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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	fura
提出日時	2020-10-09 21:56:03
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	124 ms / 2,000 ms
コード長	1,938 bytes
コンパイル時間	2,504 ms
コンパイル使用メモリ	213,832 KB
実行使用メモリ	22,132 KB
最終ジャッジ日時	2023-09-27 16:45:49
合計ジャッジ時間	14,483 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,376 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	1 ms 4,380 KB
testcase_25	AC	1 ms 4,380 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	2 ms 4,380 KB
testcase_32	AC	1 ms 4,380 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	1 ms 4,380 KB
testcase_35	AC	2 ms 4,380 KB
testcase_36	AC	2 ms 4,376 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	2 ms 4,376 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	2 ms 4,380 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	2 ms 4,376 KB
testcase_46	AC	2 ms 4,376 KB
testcase_47	AC	2 ms 4,380 KB
testcase_48	AC	2 ms 4,376 KB
testcase_49	AC	1 ms 4,376 KB
testcase_50	AC	2 ms 4,376 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,376 KB
testcase_55	AC	2 ms 4,376 KB
testcase_56	AC	2 ms 4,376 KB
testcase_57	AC	2 ms 4,380 KB
testcase_58	AC	2 ms 4,380 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	1 ms 4,380 KB
testcase_61	AC	2 ms 4,376 KB
testcase_62	AC	2 ms 4,380 KB
testcase_63	AC	8 ms 5,116 KB
testcase_64	AC	3 ms 4,380 KB
testcase_65	AC	6 ms 4,448 KB
testcase_66	AC	5 ms 4,568 KB
testcase_67	AC	3 ms 4,380 KB
testcase_68	AC	6 ms 4,380 KB
testcase_69	AC	6 ms 4,656 KB
testcase_70	AC	4 ms 4,408 KB
testcase_71	AC	3 ms 4,380 KB
testcase_72	AC	7 ms 4,900 KB
testcase_73	AC	4 ms 4,380 KB
testcase_74	AC	7 ms 4,464 KB
testcase_75	AC	5 ms 4,536 KB
testcase_76	AC	3 ms 4,380 KB
testcase_77	AC	5 ms 4,380 KB
testcase_78	AC	8 ms 4,824 KB
testcase_79	AC	8 ms 4,976 KB
testcase_80	AC	7 ms 4,644 KB
testcase_81	AC	8 ms 4,972 KB
testcase_82	AC	8 ms 4,924 KB
testcase_83	AC	112 ms 21,568 KB
testcase_84	AC	111 ms 20,972 KB
testcase_85	AC	58 ms 14,548 KB
testcase_86	AC	91 ms 18,884 KB
testcase_87	AC	100 ms 20,180 KB
testcase_88	AC	12 ms 6,092 KB
testcase_89	AC	111 ms 21,524 KB
testcase_90	AC	61 ms 14,968 KB
testcase_91	AC	45 ms 12,548 KB
testcase_92	AC	24 ms 8,124 KB
testcase_93	AC	80 ms 18,068 KB
testcase_94	AC	75 ms 16,748 KB
testcase_95	AC	72 ms 16,268 KB
testcase_96	AC	105 ms 20,628 KB
testcase_97	AC	38 ms 11,124 KB
testcase_98	AC	107 ms 20,872 KB
testcase_99	AC	58 ms 13,792 KB
testcase_100	AC	120 ms 22,132 KB
testcase_101	AC	21 ms 7,484 KB
testcase_102	AC	11 ms 5,352 KB
testcase_103	AC	23 ms 8,116 KB
testcase_104	AC	31 ms 10,008 KB
testcase_105	AC	82 ms 18,012 KB
testcase_106	AC	43 ms 12,088 KB
testcase_107	AC	112 ms 21,476 KB
testcase_108	AC	111 ms 21,308 KB
testcase_109	AC	83 ms 17,600 KB
testcase_110	AC	73 ms 16,360 KB
testcase_111	AC	80 ms 17,156 KB
testcase_112	AC	32 ms 9,744 KB
testcase_113	AC	68 ms 15,880 KB
testcase_114	AC	42 ms 11,580 KB
testcase_115	AC	13 ms 6,132 KB
testcase_116	AC	49 ms 12,820 KB
testcase_117	AC	31 ms 9,620 KB
testcase_118	AC	106 ms 20,464 KB
testcase_119	AC	54 ms 13,708 KB
testcase_120	AC	99 ms 19,804 KB
testcase_121	AC	26 ms 8,724 KB
testcase_122	AC	46 ms 12,740 KB
testcase_123	AC	2 ms 4,380 KB
testcase_124	AC	124 ms 16,880 KB
testcase_125	AC	105 ms 16,732 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 TECC(G);
	vector<int> id(n);
	rep(i,TECC.bridge_block_tree().size()) for(int u:TECC.component(i)) id[u]=i;

	vector<int> ans;
	rep(i,n) if(id[E[i].first]==id[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

結果

テストケース

ソースコード