#565466 (C++17) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	fura
提出日時	2020-10-10 01:59:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	90 ms / 2,000 ms
コード長	1,838 bytes
コンパイル時間	2,310 ms
コンパイル使用メモリ	215,920 KB
実行使用メモリ	21,876 KB
最終ジャッジ日時	2024-07-20 15:26:17
合計ジャッジ時間	12,077 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	3 ms 5,376 KB
testcase_51	AC	3 ms 5,376 KB
testcase_52	AC	3 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	3 ms 5,376 KB
testcase_58	AC	2 ms 5,376 KB
testcase_59	AC	2 ms 5,376 KB
testcase_60	AC	2 ms 5,376 KB
testcase_61	AC	2 ms 5,376 KB
testcase_62	AC	2 ms 5,376 KB
testcase_63	AC	8 ms 5,376 KB
testcase_64	AC	3 ms 5,376 KB
testcase_65	AC	6 ms 5,376 KB
testcase_66	AC	5 ms 5,376 KB
testcase_67	AC	3 ms 5,376 KB
testcase_68	AC	5 ms 5,376 KB
testcase_69	AC	7 ms 5,376 KB
testcase_70	AC	4 ms 5,376 KB
testcase_71	AC	3 ms 5,376 KB
testcase_72	AC	6 ms 5,376 KB
testcase_73	AC	4 ms 5,376 KB
testcase_74	AC	6 ms 5,376 KB
testcase_75	AC	5 ms 5,376 KB
testcase_76	AC	2 ms 5,376 KB
testcase_77	AC	4 ms 5,376 KB
testcase_78	AC	7 ms 5,376 KB
testcase_79	AC	7 ms 5,376 KB
testcase_80	AC	7 ms 5,376 KB
testcase_81	AC	8 ms 5,376 KB
testcase_82	AC	7 ms 5,376 KB
testcase_83	AC	80 ms 21,464 KB
testcase_84	AC	76 ms 21,024 KB
testcase_85	AC	47 ms 14,368 KB
testcase_86	AC	73 ms 18,716 KB
testcase_87	AC	73 ms 20,024 KB
testcase_88	AC	12 ms 6,144 KB
testcase_89	AC	78 ms 21,300 KB
testcase_90	AC	47 ms 15,000 KB
testcase_91	AC	34 ms 12,648 KB
testcase_92	AC	19 ms 8,320 KB
testcase_93	AC	63 ms 17,892 KB
testcase_94	AC	53 ms 16,476 KB
testcase_95	AC	54 ms 16,460 KB
testcase_96	AC	73 ms 20,444 KB
testcase_97	AC	30 ms 11,216 KB
testcase_98	AC	76 ms 20,636 KB
testcase_99	AC	43 ms 13,952 KB
testcase_100	AC	90 ms 21,876 KB
testcase_101	AC	19 ms 7,808 KB
testcase_102	AC	9 ms 5,632 KB
testcase_103	AC	19 ms 8,192 KB
testcase_104	AC	25 ms 9,988 KB
testcase_105	AC	61 ms 17,900 KB
testcase_106	AC	36 ms 12,032 KB
testcase_107	AC	82 ms 21,416 KB
testcase_108	AC	76 ms 21,212 KB
testcase_109	AC	62 ms 17,696 KB
testcase_110	AC	58 ms 16,408 KB
testcase_111	AC	60 ms 17,276 KB
testcase_112	AC	26 ms 9,856 KB
testcase_113	AC	51 ms 16,008 KB
testcase_114	AC	32 ms 11,792 KB
testcase_115	AC	13 ms 6,528 KB
testcase_116	AC	40 ms 13,060 KB
testcase_117	AC	26 ms 9,732 KB
testcase_118	AC	75 ms 20,388 KB
testcase_119	AC	43 ms 13,888 KB
testcase_120	AC	75 ms 19,796 KB
testcase_121	AC	23 ms 8,832 KB
testcase_122	AC	39 ms 12,856 KB
testcase_123	AC	2 ms 5,376 KB
testcase_124	AC	68 ms 16,540 KB
testcase_125	AC	70 ms 16,548 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using graph=vector<vector<int>>;

void add_undirected_edge(graph& G,int u,int v){
	G[u].emplace_back(v);
	G[v].emplace_back(u);
}

class two_edge_connected_components{
	int idx;
	vector<int> ord,low,id;
	const graph& G;

	vector<vector<int>> Comp;
	vector<pair<int,int>> B;
	graph Tr;

	void dfs1(int u,int p){
		ord[u]=low[u]=idx++;
		bool f=true;
		for(int v:G[u]){
			if(v==p && f){ f=false; continue; }
			if(ord[v]==-1){
				dfs1(v,u);
				low[u]=min(low[u],low[v]);
			}
			else{
				low[u]=min(low[u],ord[v]);
			}
		}
	}

	void dfs2(int u,int p){
		if(p==-1 || ord[p]<low[u]){
			id[u]=idx++;
			if(p!=-1) B.emplace_back(minmax(p,u));
		}
		else{
			id[u]=id[p];
		}
		for(int v:G[u]) if(id[v]==-1) dfs2(v,u);
	}

public:
	two_edge_connected_components(const graph& G):G(G){
		int n=G.size();

		idx=0;
		ord.assign(n,-1);
		low.assign(n,-1);
		rep(u,n) if(ord[u]==-1) dfs1(u,-1);

		idx=0;
		id.assign(n,-1);
		rep(u,n) if(id[u]==-1) dfs2(u,-1);

		Comp.resize(idx);
		Tr.resize(idx);
		rep(u,n){
			Comp[id[u]].emplace_back(u);
			for(int v:G[u]) if(id[u]!=id[v]) Tr[id[u]].emplace_back(id[v]);
		}
	}

	int operator[](int i)const{ return id[i]; }

	const vector<int>& component(int i)const{ return Comp[i]; }
	const vector<pair<int,int>>& bridges()const{ return B; }
	const graph& bridge_block_tree()const{ return Tr; }
};

int main(){
	int n; scanf("%d",&n);
	graph G(n);
	vector<pair<int,int>> E(n);
	rep(i,n){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		add_undirected_edge(G,u,v);
		E[i]={u,v};
	}

	two_edge_connected_components TE(G);

	vector<int> ans;
	rep(i,n) if(TE[E[i].first]==TE[E[i].second]) ans.emplace_back(i);
	printf("%ld\n",ans.size());
	rep(i,ans.size()) printf("%d%c",ans[i]+1,i+1<ans.size()?' ':'\n');

	return 0;
}

yukicoder

結果

テストケース

ソースコード