Submission #3017918


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> Pair;

struct BCC{
    vector<Pair> bridge;
    vector<vector<int>> each_bcc;
    vector<int> cmp;
    stack<int> roots;
    stack<int> S;
    vector<bool> inS;
    vector<int> order;
    int k;

    void visit(int cur, int pre, const vector<int> G[]){
        order[cur] = ++k;
        S.push(cur);
        inS[cur] = true;
        roots.push(cur);

        for(auto to : G[cur]){
            if(order[to] == 0){
                visit(to, cur, G);
            }else if(to != pre && inS[to]){
                while(order[roots.top()] > order[to]) roots.pop();
            }
        }

        if(cur == roots.top()){
            if(pre != -1) bridge.push_back({pre, cur});
            vector<int> bcc;
            while(true){
                int node = S.top();
                S.pop();
                inS[node] = false;
                bcc.push_back(node);
                cmp[node] = each_bcc.size();
                if(node == cur) break;
            }
            each_bcc.push_back(bcc);
            roots.pop();
        }
    }

    void calculate(int N, const vector<int> edges[]){
        order.resize(N, 0);
        inS.resize(N, false);
        cmp.resize(N, 0);
        k = 0;
        for(int i=0; i<N; i++){
            if(order[i] == 0) visit(i, -1, edges);
        }
    }

    int dump_graph(int N, const vector<int> edges[], vector<int> edges2[]){
        for(int i=0; i<N; i++){
            for(auto j : edges[i]){
                if(cmp[i] != cmp[j]){
                    edges2[cmp[i]].push_back(cmp[j]);
                }
            }
        }
        return *max_element(cmp.begin(), cmp.end()) + 1;  
    }
};

struct LCA{
    static const int BITLEN = 30;
    vector<int> parent[BITLEN];
    vector<int> depth;
    int bitlen;

    void initialize(int N, const vector<int> edges[]){
        int root = 0;
        bitlen = 1;
        while((1<<bitlen) < N) bitlen <<= 1;
        for(int i=0; i<bitlen; i++) parent[i].resize(N);
        depth.resize(N, -1);

        dfs(root, -1, 0, edges);
        for(int k=0; k<bitlen-1; k++){
            for(int v=0; v<N; v++){
                if(depth[v] == -1) continue;
                if(parent[k][v] < 0){
                    parent[k+1][v] = -1;
                }else{
                    parent[k+1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(int v, int p, int d, const vector<int> edges[]){
        parent[0][v] = p;
        depth[v] = d;
        for(auto u : edges[v]){
            if(u != p) dfs(u, v, d+1, edges);
        }
    }

    int lca(int u, int v){
        if(depth[u] > depth[v]) swap(u, v);
        for(int k=0; k<bitlen; k++){
            if( ((depth[v]-depth[u]) >> k) & 1 ) v = parent[k][v];
        }
        if(u == v) return u;
        for(int k=bitlen-1; k>=0; k--){
            if(parent[k][u] != parent[k][v]){
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    int dist(int u, int v){
        int l = lca(u, v);
        return depth[u] + depth[v] - depth[l]*2;
    }
};

int main(){
    int i, j, k;
    int N, M;
    cin >> N >> M;
    const int MAX = 100000;
    vector<int> edges[MAX];
    for(i=0; i<M; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        edges[x-1].push_back(y-1);
        edges[y-1].push_back(x-1);
    }

    BCC bcc;
    bcc.calculate(N, edges);
    // vector<int> edges2[MAX];
    // int N2 = bcc.dump_graph(N, edges, edges2);
    // LCA lca;
    // lca.initialize(N2, edges2);

    // int Q;
    // cin >> Q;
    // for(i=0; i<Q; i++){
    //     int a, b, c;
    //     scanf("%d %d %d", &a, &b, &c);
    //     a = bcc.cmp[a-1];
    //     b = bcc.cmp[b-1];
    //     c = bcc.cmp[c-1];
    //     int d1 = lca.dist(a, c);
    //     int d2 = lca.dist(a, b) + lca.dist(b, c);
    //     printf("%s\n", (d1==d2 ? "OK" : "NG"));
    // }
    return 0;
}

Submission Info

Submission Time
Task D - 旅行会社高橋君
User betrue12
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4142 Byte
Status WA
Exec Time 82 ms
Memory 25000 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:131:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 3
WA × 80
Set Name Test Cases
Sample sample_0.txt, sample_1.txt, sample_2.txt
All bigcycleandsub_0.txt, bigcycleandsub_1.txt, cluster_0.txt, cluster_1.txt, cluster_2.txt, cluster_3.txt, cluster_4.txt, cycleline_0.txt, cycleline_1.txt, cycleline_2.txt, cycleline_3.txt, cycleline_4.txt, cycletree_0.txt, cycletree_1.txt, cycletree_2.txt, cycletree_3.txt, cycletree_4.txt, large_0.txt, large_1.txt, large_2.txt, line_0.txt, line_1.txt, lineandsub_0.txt, lineandsub_1.txt, lineandsub_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_2.txt, maxrandandsub_0.txt, maxrandandsub_1.txt, maxrandandsub_2.txt, maxrandandsub_3.txt, maxrandandsub_4.txt, med_0.txt, med_1.txt, med_2.txt, med_3.txt, med_4.txt, med_5.txt, med_6.txt, med_7.txt, med_8.txt, med_9.txt, perfect_0.txt, perfect_1.txt, perfect_2.txt, sample_0.txt, sample_1.txt, sample_2.txt, small_0.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt, star_0.txt, star_1.txt, star_2.txt, tencluster_0.txt, tencluster_1.txt, tencluster_2.txt, tencluster_3.txt, tencluster_4.txt, tree_0.txt, tree_1.txt, tree_2.txt, verysmall_0.txt, verysmall_1.txt, verysmall_2.txt, verysmall_3.txt, verysmall_4.txt, verysmall_5.txt, verysmall_6.txt, verysmall_7.txt, verysmall_8.txt, verysmall_9.txt
Case Name Status Exec Time Memory
bigcycleandsub_0.txt WA 45 ms 19896 KB
bigcycleandsub_1.txt WA 45 ms 19896 KB
cluster_0.txt WA 64 ms 8960 KB
cluster_1.txt WA 65 ms 8960 KB
cluster_2.txt WA 64 ms 8704 KB
cluster_3.txt WA 65 ms 8960 KB
cluster_4.txt WA 65 ms 8704 KB
cycleline_0.txt WA 41 ms 7936 KB
cycleline_1.txt WA 41 ms 7808 KB
cycleline_2.txt WA 41 ms 7680 KB
cycleline_3.txt WA 41 ms 7680 KB
cycleline_4.txt WA 41 ms 7936 KB
cycletree_0.txt WA 42 ms 7296 KB
cycletree_1.txt WA 41 ms 7296 KB
cycletree_2.txt WA 41 ms 7296 KB
cycletree_3.txt WA 41 ms 7296 KB
cycletree_4.txt WA 41 ms 7296 KB
large_0.txt WA 75 ms 17776 KB
large_1.txt WA 12 ms 4736 KB
large_2.txt WA 53 ms 17460 KB
line_0.txt WA 55 ms 25000 KB
line_1.txt WA 53 ms 22692 KB
lineandsub_0.txt WA 54 ms 21160 KB
lineandsub_1.txt WA 55 ms 24492 KB
lineandsub_2.txt WA 53 ms 23208 KB
maxrand_0.txt WA 79 ms 21364 KB
maxrand_1.txt WA 82 ms 21232 KB
maxrand_2.txt WA 80 ms 21352 KB
maxrandandsub_0.txt WA 78 ms 20536 KB
maxrandandsub_1.txt WA 81 ms 20536 KB
maxrandandsub_2.txt WA 81 ms 20664 KB
maxrandandsub_3.txt WA 80 ms 20536 KB
maxrandandsub_4.txt WA 80 ms 20664 KB
med_0.txt WA 2 ms 2688 KB
med_1.txt WA 2 ms 2560 KB
med_2.txt WA 3 ms 2688 KB
med_3.txt WA 2 ms 2688 KB
med_4.txt WA 2 ms 2688 KB
med_5.txt WA 3 ms 2688 KB
med_6.txt WA 3 ms 2688 KB
med_7.txt WA 3 ms 2688 KB
med_8.txt WA 2 ms 2560 KB
med_9.txt WA 2 ms 2688 KB
perfect_0.txt WA 16 ms 3456 KB
perfect_1.txt WA 18 ms 3584 KB
perfect_2.txt WA 16 ms 3584 KB
sample_0.txt WA 2 ms 2560 KB
sample_1.txt WA 2 ms 2560 KB
sample_2.txt WA 2 ms 2560 KB
small_0.txt WA 2 ms 2560 KB
small_1.txt WA 2 ms 2560 KB
small_2.txt WA 2 ms 2560 KB
small_3.txt WA 2 ms 2560 KB
small_4.txt WA 2 ms 2560 KB
small_5.txt WA 2 ms 2560 KB
small_6.txt WA 2 ms 2560 KB
small_7.txt WA 2 ms 2560 KB
small_8.txt WA 2 ms 2560 KB
small_9.txt WA 2 ms 2560 KB
star_0.txt WA 43 ms 13160 KB
star_1.txt WA 43 ms 13160 KB
star_2.txt WA 43 ms 13804 KB
tencluster_0.txt WA 69 ms 10492 KB
tencluster_1.txt WA 66 ms 9980 KB
tencluster_2.txt WA 65 ms 9728 KB
tencluster_3.txt WA 69 ms 10752 KB
tencluster_4.txt WA 66 ms 10752 KB
tree_0.txt WA 55 ms 12840 KB
tree_1.txt WA 55 ms 13612 KB
tree_2.txt WA 55 ms 12840 KB
verysmall_0.txt WA 2 ms 2560 KB
verysmall_1.txt WA 2 ms 2560 KB
verysmall_2.txt WA 2 ms 2560 KB
verysmall_3.txt WA 2 ms 2560 KB
verysmall_4.txt WA 2 ms 2560 KB
verysmall_5.txt WA 2 ms 2560 KB
verysmall_6.txt WA 2 ms 2560 KB
verysmall_7.txt WA 2 ms 2560 KB
verysmall_8.txt WA 2 ms 2560 KB
verysmall_9.txt WA 2 ms 2560 KB