東京大学プログラミングコンテスト2014

Submission #1015041

Source codeソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)
 
 
//橋・二重辺連結成分の列挙 verified 天下一プロコン2015qualA-D
#define MAX_V 100000
vector<int> G[MAX_V];
 
void visit(int cur, int prev, vector<pii> &brg, vector<vector<int>> &each_bcc, vector<int> &cmp, stack<int> &roots, stack<int> &S, vector<bool> &inS, vector<int> &order, int &k){
	order[cur] = ++k;		//頂点を訪れた順に順序付け
	S.push(cur); inS[cur] = true;	//訪れた頂点の集合を管理
	roots.push(cur);		//各二重辺連結成分をDFS木の部分木として見たときの、根を管理
	
	rep(i,G[cur].size()){
		int to = G[cur][i];
		if(order[to]==0){
			visit(to,cur,brg,each_bcc,cmp,roots,S,inS,order,k);
		}
		else if(to!=prev && inS[to]){	//後退辺をたどる
			while(order[roots.top()] > order[to]) roots.pop();	//cur〜toまで(toは含まない)の頂点をrootsから捨てる
		}
	}
	
	if(cur==roots.top()){	//オイラーツアーみたいなのを考えて、葉側から根側に橋を渡るとき、条件式がTRUEになる
		if(prev!=-1)brg.pb(pii(prev,cur));
		vector<int> bcc;
		while(1){
			int node = S.top(); S.pop(); inS[node] = false;	//集合Sからnodeを捨てる
			bcc.pb(node);					//nodeを二重辺連結成分に追加
			cmp[node] = each_bcc.size();
			if(node==cur)break;
		}
		each_bcc.pb(bcc);
		roots.pop();
	}
}
 
 
void bridge(int V, vector<pii> &brg, vector<vector<int>> &each_bcc, vector<int> &cmp){	//橋の列挙と二重辺連結成分分解を同時に行う
	vector<int> order(V);
	vector<bool> inS(V);
	stack<int> roots, S;
	int k=0;
	rep(i,V){
		if(order[i]==0){
			visit(i,-1,brg,each_bcc,cmp,roots,S,inS,order,k);
		}
	}
}
 
 
int main(){
	int v;
	cin>>v;
	rep(i,v){
		int a,b;
		cin>>a>>b;
		a--,b--;
		G[a].pb(b);
		G[b].pb(a);
	}
 
	vector<pii> brg;		//橋のリスト
	vector<vector<int>> each_bcc;	//二重辺連結成分のリスト
	vector<int> cmp(v);		//cmp[i] = 頂点iが所属している二重辺連結成分の番号
	bridge(v,brg,each_bcc,cmp);
	
	
	int circle_size = 0;
	rep(i,each_bcc.size())circle_size = max<int>( circle_size , each_bcc[i].size() );
	
	if(circle_size%2!=0)v--;
	
	if(each_bcc.size()>1)	cout<<1<<" "<<v<<endl;
	else					cout<<2<<" "<<v<<endl;
	
}

Submission

Task問題 C - 最小カットと最大カット
User nameユーザ名 Yazaten
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 2514 Byte
File nameファイル名
Exec time実行時間 136 ms
Memory usageメモリ使用量 26872 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 scrambled_00.txt,scrambled_01.txt,scrambled_02.txt,scrambled_03.txt,scrambled_04.txt,scrambled_05.txt,scrambled_06.txt,scrambled_07.txt,scrambled_08.txt,scrambled_09.txt,scrambled_10.txt,scrambled_11.txt,scrambled_12.txt,scrambled_13.txt,scrambled_14.txt,scrambled_15.txt,scrambled_16.txt,scrambled_17.txt,scrambled_18.txt,scrambled_19.txt,scrambled_20.txt,scrambled_21.txt,scrambled_22.txt,scrambled_23.txt,scrambled_24.txt,scrambled_25.txt,scrambled_26.txt,scrambled_27.txt,scrambled_28.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
scrambled_00.txt AC 22 ms 3228 KB
scrambled_01.txt AC 20 ms 3228 KB
scrambled_02.txt AC 21 ms 3228 KB
scrambled_03.txt AC 136 ms 26812 KB
scrambled_04.txt AC 133 ms 26872 KB
scrambled_05.txt AC 87 ms 17968 KB
scrambled_06.txt AC 64 ms 12576 KB
scrambled_07.txt AC 123 ms 25012 KB
scrambled_08.txt AC 54 ms 10604 KB
scrambled_09.txt AC 65 ms 12924 KB
scrambled_10.txt AC 115 ms 13704 KB
scrambled_11.txt AC 58 ms 7504 KB
scrambled_12.txt AC 98 ms 12128 KB
scrambled_13.txt AC 97 ms 11908 KB
scrambled_14.txt AC 134 ms 13256 KB
scrambled_15.txt AC 95 ms 11476 KB
scrambled_16.txt AC 59 ms 7380 KB
scrambled_17.txt AC 59 ms 7388 KB
scrambled_18.txt AC 124 ms 13336 KB
scrambled_19.txt AC 28 ms 4252 KB
scrambled_20.txt AC 82 ms 9488 KB
scrambled_21.txt AC 59 ms 7464 KB
scrambled_22.txt AC 92 ms 11552 KB
scrambled_23.txt AC 63 ms 7588 KB
scrambled_24.txt AC 61 ms 7508 KB
scrambled_25.txt AC 71 ms 8276 KB
scrambled_26.txt AC 62 ms 7512 KB
scrambled_27.txt AC 82 ms 9372 KB
scrambled_28.txt AC 77 ms 8860 KB