#565034 (C++14) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	suta28407928
提出日時	2020-10-09 22:58:55
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	321 ms / 2,000 ms
コード長	3,262 bytes
コンパイル時間	1,901 ms
コンパイル使用メモリ	139,120 KB
実行使用メモリ	33,408 KB
最終ジャッジ日時	2024-07-20 13:42:27
合計ジャッジ時間	17,546 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	1 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,944 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	2 ms 6,944 KB
testcase_43	AC	4 ms 6,944 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	3 ms 6,940 KB
testcase_46	AC	3 ms 6,940 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	3 ms 6,944 KB
testcase_49	AC	2 ms 6,940 KB
testcase_50	AC	3 ms 6,944 KB
testcase_51	AC	3 ms 6,944 KB
testcase_52	AC	3 ms 6,944 KB
testcase_53	AC	3 ms 6,940 KB
testcase_54	AC	3 ms 6,944 KB
testcase_55	AC	3 ms 6,944 KB
testcase_56	AC	2 ms 6,940 KB
testcase_57	AC	3 ms 6,940 KB
testcase_58	AC	2 ms 6,940 KB
testcase_59	AC	2 ms 6,940 KB
testcase_60	AC	2 ms 6,940 KB
testcase_61	AC	3 ms 6,944 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	19 ms 6,944 KB
testcase_64	AC	6 ms 6,940 KB
testcase_65	AC	13 ms 6,944 KB
testcase_66	AC	10 ms 6,940 KB
testcase_67	AC	5 ms 6,944 KB
testcase_68	AC	10 ms 6,940 KB
testcase_69	AC	15 ms 6,944 KB
testcase_70	AC	7 ms 6,944 KB
testcase_71	AC	5 ms 6,948 KB
testcase_72	AC	15 ms 6,940 KB
testcase_73	AC	6 ms 6,940 KB
testcase_74	AC	14 ms 6,944 KB
testcase_75	AC	11 ms 6,944 KB
testcase_76	AC	4 ms 6,940 KB
testcase_77	AC	9 ms 6,940 KB
testcase_78	AC	17 ms 6,944 KB
testcase_79	AC	18 ms 6,940 KB
testcase_80	AC	16 ms 6,944 KB
testcase_81	AC	19 ms 6,940 KB
testcase_82	AC	17 ms 6,940 KB
testcase_83	AC	307 ms 27,048 KB
testcase_84	AC	321 ms 26,520 KB
testcase_85	AC	152 ms 17,772 KB
testcase_86	AC	269 ms 23,384 KB
testcase_87	AC	274 ms 25,184 KB
testcase_88	AC	29 ms 6,940 KB
testcase_89	AC	309 ms 27,024 KB
testcase_90	AC	176 ms 18,632 KB
testcase_91	AC	126 ms 15,424 KB
testcase_92	AC	62 ms 9,728 KB
testcase_93	AC	237 ms 22,312 KB
testcase_94	AC	195 ms 20,684 KB
testcase_95	AC	200 ms 20,508 KB
testcase_96	AC	297 ms 25,736 KB
testcase_97	AC	113 ms 13,768 KB
testcase_98	AC	286 ms 25,916 KB
testcase_99	AC	153 ms 17,268 KB
testcase_100	AC	319 ms 27,528 KB
testcase_101	AC	52 ms 9,088 KB
testcase_102	AC	27 ms 6,944 KB
testcase_103	AC	59 ms 9,600 KB
testcase_104	AC	87 ms 12,084 KB
testcase_105	AC	227 ms 22,320 KB
testcase_106	AC	112 ms 14,720 KB
testcase_107	AC	308 ms 26,916 KB
testcase_108	AC	308 ms 26,572 KB
testcase_109	AC	242 ms 22,012 KB
testcase_110	AC	204 ms 20,384 KB
testcase_111	AC	219 ms 21,440 KB
testcase_112	AC	76 ms 11,648 KB
testcase_113	AC	190 ms 19,948 KB
testcase_114	AC	108 ms 14,256 KB
testcase_115	AC	32 ms 7,296 KB
testcase_116	AC	131 ms 15,896 KB
testcase_117	AC	77 ms 11,760 KB
testcase_118	AC	284 ms 25,472 KB
testcase_119	AC	143 ms 16,988 KB
testcase_120	AC	267 ms 24,788 KB
testcase_121	AC	63 ms 10,368 KB
testcase_122	AC	130 ms 15,824 KB
testcase_123	AC	2 ms 6,940 KB
testcase_124	AC	271 ms 33,408 KB
testcase_125	AC	267 ms 33,280 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <ctime>
#include <complex>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-10;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    for(auto itr = a.begin(); itr != a.end(); itr++){
		cout << *itr << " ";
	}
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){
	cout << "debug: " << a << " " << b << "\n";
}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << "debug: " << a << " " << b << " " << c << "\n";
}
void mark() {cout << "#" << "\n";}
ll pcount(ll x) {return __builtin_popcountll(x);}
const int mod = 1e9 + 7;
//const int mod = 998244353;

template< typename G >
struct LowLink {
  const G &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;
 
  LowLink(const G &g) : g(g) {}
 
  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }
 
  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

map<P,int> mp;

int main(){
	int n; cin >> n;
	vvl G(n);
	rep(i,n){
		int a,b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
		mp[{a,b}] = i;
		mp[{b,a}] = i;
	}
	LowLink<vvl> low(G);
	low.build();
	set<int> se;
	rep(i,n) se.insert(i+1);
	for(auto i : low.bridge){
		se.erase(mp[i]+1);
	}
	cout << se.size() << "\n";
	print(se);
}

yukicoder

結果

テストケース

ソースコード