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