Submission #6530044
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
// from https://utpc2014.contest.atcoder.jp/submissions/1015041
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 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);
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();
}
}
if(cur==roots.top()){
if(prev!=-1)brg.pb(pii(prev,cur));
vector<int> bcc;
while(1){
int node=S.top(); S.pop(); inS[node]=false;
bcc.pb(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 n;
scanf("%d",&n);
rep(i,n){
int a,b;
scanf("%d %d",&a,&b);
a--,b--;
G[a].pb(b);
G[b].pb(a);
}
vector<pii> brg;
vector<vector<int>> each_bcc;
vector<int> cmp(n);
bridge(n,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) n--;
if (each_bcc.size()>1) printf("1 %d\n",n);
else printf("2 %d\n",n);
//printf("%d\n",n);
return 0;
}
Submission Info
Submission Time
2019-07-25 02:27:25+0900
Task
C - 最小カットと最大カット
User
nyon
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2028 Byte
Status
AC
Exec Time
65 ms
Memory
24796 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:54:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:57:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
^
Judge Result
Set Name
All
Score / Max Score
100 / 100
Status
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
2 ms
2560 KB
scrambled_01.txt
AC
2 ms
2560 KB
scrambled_02.txt
AC
2 ms
2560 KB
scrambled_03.txt
AC
55 ms
24796 KB
scrambled_04.txt
AC
57 ms
24796 KB
scrambled_05.txt
AC
32 ms
16528 KB
scrambled_06.txt
AC
20 ms
11392 KB
scrambled_07.txt
AC
49 ms
23072 KB
scrambled_08.txt
AC
17 ms
9596 KB
scrambled_09.txt
AC
21 ms
11736 KB
scrambled_10.txt
AC
45 ms
13160 KB
scrambled_11.txt
AC
18 ms
7088 KB
scrambled_12.txt
AC
36 ms
11628 KB
scrambled_13.txt
AC
34 ms
11500 KB
scrambled_14.txt
AC
56 ms
12708 KB
scrambled_15.txt
AC
39 ms
11052 KB
scrambled_16.txt
AC
21 ms
6832 KB
scrambled_17.txt
AC
21 ms
6836 KB
scrambled_18.txt
AC
65 ms
12836 KB
scrambled_19.txt
AC
6 ms
3712 KB
scrambled_20.txt
AC
34 ms
9008 KB
scrambled_21.txt
AC
21 ms
6964 KB
scrambled_22.txt
AC
39 ms
11948 KB
scrambled_23.txt
AC
24 ms
7088 KB
scrambled_24.txt
AC
22 ms
6960 KB
scrambled_25.txt
AC
28 ms
7728 KB
scrambled_26.txt
AC
23 ms
7092 KB
scrambled_27.txt
AC
34 ms
8880 KB
scrambled_28.txt
AC
31 ms
8364 KB