#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
実行時間	80 ms / 2,000 ms
コード長	1,838 bytes
コンパイル時間	2,508 ms
コンパイル使用メモリ	214,648 KB
実行使用メモリ	21,516 KB
最終ジャッジ日時	2023-09-27 20:53:58
合計ジャッジ時間	13,051 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,380 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	1 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	1 ms 4,380 KB
testcase_25	AC	1 ms 4,384 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	2 ms 4,376 KB
testcase_29	AC	1 ms 4,380 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	1 ms 4,380 KB
testcase_32	AC	1 ms 4,380 KB
testcase_33	AC	1 ms 4,380 KB
testcase_34	AC	1 ms 4,380 KB
testcase_35	AC	1 ms 4,376 KB
testcase_36	AC	1 ms 4,380 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	2 ms 4,376 KB
testcase_40	AC	1 ms 4,376 KB
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	1 ms 4,380 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	2 ms 4,380 KB
testcase_46	AC	2 ms 4,380 KB
testcase_47	AC	2 ms 4,380 KB
testcase_48	AC	2 ms 4,380 KB
testcase_49	AC	1 ms 4,380 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	2 ms 4,376 KB
testcase_52	AC	2 ms 4,376 KB
testcase_53	AC	2 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	1 ms 4,380 KB
testcase_56	AC	2 ms 4,380 KB
testcase_57	AC	2 ms 4,376 KB
testcase_58	AC	2 ms 4,380 KB
testcase_59	AC	2 ms 4,380 KB
testcase_60	AC	2 ms 4,380 KB
testcase_61	AC	3 ms 4,380 KB
testcase_62	AC	1 ms 4,376 KB
testcase_63	AC	8 ms 5,036 KB
testcase_64	AC	3 ms 4,376 KB
testcase_65	AC	5 ms 4,408 KB
testcase_66	AC	5 ms 4,504 KB
testcase_67	AC	2 ms 4,380 KB
testcase_68	AC	4 ms 4,380 KB
testcase_69	AC	6 ms 4,468 KB
testcase_70	AC	3 ms 4,376 KB
testcase_71	AC	3 ms 4,380 KB
testcase_72	AC	7 ms 4,820 KB
testcase_73	AC	3 ms 4,380 KB
testcase_74	AC	5 ms 4,568 KB
testcase_75	AC	5 ms 4,584 KB
testcase_76	AC	2 ms 4,376 KB
testcase_77	AC	4 ms 4,376 KB
testcase_78	AC	7 ms 4,860 KB
testcase_79	AC	7 ms 4,960 KB
testcase_80	AC	6 ms 4,768 KB
testcase_81	AC	7 ms 4,964 KB
testcase_82	AC	6 ms 4,948 KB
testcase_83	AC	74 ms 21,328 KB
testcase_84	AC	74 ms 20,664 KB
testcase_85	AC	41 ms 14,324 KB
testcase_86	AC	62 ms 18,624 KB
testcase_87	AC	69 ms 19,956 KB
testcase_88	AC	11 ms 5,772 KB
testcase_89	AC	70 ms 21,156 KB
testcase_90	AC	44 ms 14,644 KB
testcase_91	AC	35 ms 12,492 KB
testcase_92	AC	19 ms 7,956 KB
testcase_93	AC	59 ms 17,736 KB
testcase_94	AC	53 ms 16,300 KB
testcase_95	AC	51 ms 16,204 KB
testcase_96	AC	68 ms 20,396 KB
testcase_97	AC	29 ms 10,968 KB
testcase_98	AC	70 ms 20,336 KB
testcase_99	AC	41 ms 13,756 KB
testcase_100	AC	78 ms 21,516 KB
testcase_101	AC	17 ms 7,512 KB
testcase_102	AC	10 ms 5,420 KB
testcase_103	AC	19 ms 8,036 KB
testcase_104	AC	26 ms 9,976 KB
testcase_105	AC	59 ms 17,800 KB
testcase_106	AC	33 ms 11,748 KB
testcase_107	AC	74 ms 21,164 KB
testcase_108	AC	80 ms 20,896 KB
testcase_109	AC	62 ms 17,400 KB
testcase_110	AC	52 ms 16,048 KB
testcase_111	AC	60 ms 17,036 KB
testcase_112	AC	26 ms 9,304 KB
testcase_113	AC	50 ms 15,684 KB
testcase_114	AC	32 ms 11,380 KB
testcase_115	AC	12 ms 6,200 KB
testcase_116	AC	37 ms 12,724 KB
testcase_117	AC	25 ms 9,468 KB
testcase_118	AC	73 ms 19,872 KB
testcase_119	AC	45 ms 13,484 KB
testcase_120	AC	79 ms 19,580 KB
testcase_121	AC	22 ms 8,768 KB
testcase_122	AC	38 ms 12,468 KB
testcase_123	AC	1 ms 4,376 KB
testcase_124	AC	66 ms 16,328 KB
testcase_125	AC	67 ms 16,336 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

結果

テストケース

ソースコード