提出 #371276

ソースコード 拡げる

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
vector<int> G[100001];
int x[100001],d[100001];
int dfs(int v,int p,int t){
	x[v]=t;
	for(int u:G[v]){
		if(u==p) continue;
		if(x[u]==-1){
			int tmp=dfs(u,v,1-t);
			if(tmp>=0) return tmp;
		}else{
			if(t==x[u]) return 1;
			else return 0;
		}
	}
	return -1;
}
int main(){
	int n;
	cin>>n;
	rep(i,n){
		int a,b;
		cin>>a>>b;
		G[a-1].pb(b-1);
		G[b-1].pb(a-1);
		d[a-1]++;
		d[b-1]++;
	}
	rep(i,n) x[i]=-1;
	int mn=2;
	rep(i,n) if(d[i]==1) mn=1;
	cout<<mn<<" "<<n-dfs(0,-1,0)<<endl;
}

提出情報

提出日時
問題 C - 最小カットと最大カット
ユーザ SAT3
言語 C++11 (GCC 4.9.2)
得点 100
コード長 867 Byte
結果 AC
実行時間 195 ms
メモリ 13220 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 29
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
scrambled_00.txt AC 30 ms 3116 KiB
scrambled_01.txt AC 29 ms 3104 KiB
scrambled_02.txt AC 29 ms 3096 KiB
scrambled_03.txt AC 190 ms 13216 KiB
scrambled_04.txt AC 195 ms 13220 KiB
scrambled_05.txt AC 192 ms 9424 KiB
scrambled_06.txt AC 88 ms 7072 KiB
scrambled_07.txt AC 184 ms 12444 KiB
scrambled_08.txt AC 73 ms 6172 KiB
scrambled_09.txt AC 87 ms 7200 KiB
scrambled_10.txt AC 157 ms 7332 KiB
scrambled_11.txt AC 74 ms 4760 KiB
scrambled_12.txt AC 129 ms 6564 KiB
scrambled_13.txt AC 123 ms 6296 KiB
scrambled_14.txt AC 172 ms 6956 KiB
scrambled_15.txt AC 127 ms 5916 KiB
scrambled_16.txt AC 80 ms 4524 KiB
scrambled_17.txt AC 79 ms 4520 KiB
scrambled_18.txt AC 176 ms 7152 KiB
scrambled_19.txt AC 37 ms 3488 KiB
scrambled_20.txt AC 113 ms 5548 KiB
scrambled_21.txt AC 77 ms 4640 KiB
scrambled_22.txt AC 120 ms 5924 KiB
scrambled_23.txt AC 86 ms 4848 KiB
scrambled_24.txt AC 81 ms 4640 KiB
scrambled_25.txt AC 95 ms 5148 KiB
scrambled_26.txt AC 83 ms 4768 KiB
scrambled_27.txt AC 113 ms 5544 KiB
scrambled_28.txt AC 106 ms 5284 KiB