Submission #1015041


Source Code Expand

#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 Info

Submission Time
Task C - 最小カットと最大カット
User Yazaten
Language C++11 (GCC 4.9.2)
Score 100
Code Size 2514 Byte
Status AC
Exec Time 136 ms
Memory 26872 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 29
Set Name Test Cases
All 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
Case Name Status Exec Time Memory
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