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

Submission #6530044

Source codeソースコード

#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

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

Compiler messageコンパイルメッセージ

./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);
^

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