oj.uz

Submission #217116

# Submission time Handle Problem Language Result Execution time Memory
217116 2020-03-29T02:57:31 Z anonymous Capital City (JOI20_capital_city) C++14
100 / 100
 766 ms 32372 KB 
#include<iostream>
#include<set>
#include<vector>
#include<cassert>
#define MAXN 200005
using namespace std;
int N, K, best = 1<<30, C[MAXN];
vector <int> adj[MAXN], type[MAXN]; //adj and towns in each city
int cmp[MAXN], id = 1;
//Solve for a node
int par[MAXN];
bool done[MAXN];
vector <int> S;
set <int> Used;
void reroot(int u, int prev) {
    if (cmp[u] != cmp[prev]) {return;}
    par[u] = prev, done[u]=false;
    for (auto v: adj[u]) {if (v != prev) {reroot(v, u);}}
}

int slv(int v) { //centre v
    int ans = 0;
    S.clear();
    Used.clear();
    reroot(v, v);
    Used.insert(C[v]);
    par[v] = 0;
    for (auto k: type[C[v]]) {
        if (cmp[k] != cmp[v]) {
            return(1<<30);
        } else {
            S.push_back(k);
        }
    }
    while (S.size()) {
        int cur = S.back();
        S.pop_back();
        while (cur != 0 && !done[cur]) {
          done[cur] = true;
          if (Used.find(C[cur]) == Used.end()) {
            for (auto k: type[C[cur]]) {
                if (cmp[k] != cmp[cur]) {
                    return(1<<30);
                } else {
                    S.push_back(k);
                }
            }
            Used.insert(C[cur]);
          }
          cur = par[cur];
        }
    }
    return(Used.size());
}

//Centroid decomp
int Size[MAXN];
int resize(int u, int prev) {
     if (cmp[u] != cmp[prev]) {return(0);}
     Size[u] = 1;
     for (auto v: adj[u]) {
        if (v != prev) {Size[u] += resize(v,u);}
     }
     //printf("Size[%d] = %d\n",u,Size[u]);
     return(Size[u]);
}

int FindCentroid(int rt, int u, int prev) {
     if (cmp[u] != cmp[prev]) {return(-1);}
     int MaxSz = 0, SumSz=1;
     for (auto v: adj[u]) {
        if (v != prev && cmp[v] == cmp[u]) {
            MaxSz = max(MaxSz, Size[v]);
            SumSz += Size[v];
        }
     }
     //printf("%d %d %d\n", Size[rt], MaxSz, SumSz);
     if (2*MaxSz <= Size[rt]+1 && 2*SumSz + 1 >= Size[rt]) {
        return(u);
     }
     for (auto v: adj[u]) {
        if (v == prev) {continue;}
        int res = FindCentroid(rt, v, u);
        if (res > 0) {return(res);}
     }
     return(-1);
}

void relabel(int u, int prev, int cmp_prev) {
    if (cmp[u] != cmp_prev) {return;}
    cmp[u] = id;
    for (auto v: adj[u]) {
        if (v != prev) {relabel(v,u,cmp_prev);}
    }
}

void decomp(int u) {
    //printf("Decomp Node %d: cmp %d\n", u,cmp[u]);
    resize(u, u);
    int cent = Size[u] > 1 ? FindCentroid(u, u, u) : u;
    //printf("Chosen Centroid: %d\n",cent);
    assert(cent > 0);
    best = min(best, slv(cent));
    //cmp[cent] = -1;
    for (auto v: adj[cent]) {
        if (cmp[v] != cmp[cent]) {continue;}
        relabel(v, cent, cmp[cent]);
        id++;
        decomp(v);
    }
}

int main() {
    //freopen("capin.txt","r",stdin);
    scanf("%d %d", &N, &K);
    for (int i=1; i<N; i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i=1; i<=N; i++) {
        scanf("%d",&C[i]);
        type[C[i]].push_back(i);
    }
    decomp(1);
    printf("%d\n",best-1);
}

Compilation message

capital_city.cpp: In function 'int slv(int)':
capital_city.cpp:22:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans = 0;
         ^~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&C[i]);
         ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9780 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9780 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9856 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 12 ms 9856 KB Output is correct
16 Correct 12 ms 9856 KB Output is correct
17 Correct 11 ms 9984 KB Output is correct
18 Correct 11 ms 9960 KB Output is correct
19 Correct 11 ms 9984 KB Output is correct
20 Correct 11 ms 9984 KB Output is correct
21 Correct 12 ms 9856 KB Output is correct
22 Correct 12 ms 9984 KB Output is correct
23 Correct 11 ms 9984 KB Output is correct
24 Correct 12 ms 9856 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 14 ms 9984 KB Output is correct
27 Correct 12 ms 9984 KB Output is correct
28 Correct 12 ms 9856 KB Output is correct
29 Correct 12 ms 9856 KB Output is correct
30 Correct 12 ms 9984 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 31608 KB Output is correct
2 Correct 255 ms 31864 KB Output is correct
3 Correct 630 ms 31480 KB Output is correct
4 Correct 247 ms 31864 KB Output is correct
5 Correct 620 ms 30072 KB Output is correct
6 Correct 247 ms 31864 KB Output is correct
7 Correct 623 ms 30528 KB Output is correct
8 Correct 256 ms 32372 KB Output is correct
9 Correct 730 ms 29808 KB Output is correct
10 Correct 737 ms 28400 KB Output is correct
11 Correct 751 ms 30060 KB Output is correct
12 Correct 759 ms 31604 KB Output is correct
13 Correct 740 ms 28036 KB Output is correct
14 Correct 745 ms 31672 KB Output is correct
15 Correct 758 ms 31540 KB Output is correct
16 Correct 735 ms 28532 KB Output is correct
17 Correct 748 ms 29040 KB Output is correct
18 Correct 750 ms 29168 KB Output is correct
19 Correct 766 ms 30960 KB Output is correct
20 Correct 764 ms 32180 KB Output is correct
21 Correct 9 ms 9728 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9780 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9856 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 12 ms 9856 KB Output is correct
16 Correct 12 ms 9856 KB Output is correct
17 Correct 11 ms 9984 KB Output is correct
18 Correct 11 ms 9960 KB Output is correct
19 Correct 11 ms 9984 KB Output is correct
20 Correct 11 ms 9984 KB Output is correct
21 Correct 12 ms 9856 KB Output is correct
22 Correct 12 ms 9984 KB Output is correct
23 Correct 11 ms 9984 KB Output is correct
24 Correct 12 ms 9856 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 14 ms 9984 KB Output is correct
27 Correct 12 ms 9984 KB Output is correct
28 Correct 12 ms 9856 KB Output is correct
29 Correct 12 ms 9856 KB Output is correct
30 Correct 12 ms 9984 KB Output is correct
31 Correct 612 ms 31608 KB Output is correct
32 Correct 255 ms 31864 KB Output is correct
33 Correct 630 ms 31480 KB Output is correct
34 Correct 247 ms 31864 KB Output is correct
35 Correct 620 ms 30072 KB Output is correct
36 Correct 247 ms 31864 KB Output is correct
37 Correct 623 ms 30528 KB Output is correct
38 Correct 256 ms 32372 KB Output is correct
39 Correct 730 ms 29808 KB Output is correct
40 Correct 737 ms 28400 KB Output is correct
41 Correct 751 ms 30060 KB Output is correct
42 Correct 759 ms 31604 KB Output is correct
43 Correct 740 ms 28036 KB Output is correct
44 Correct 745 ms 31672 KB Output is correct
45 Correct 758 ms 31540 KB Output is correct
46 Correct 735 ms 28532 KB Output is correct
47 Correct 748 ms 29040 KB Output is correct
48 Correct 750 ms 29168 KB Output is correct
49 Correct 766 ms 30960 KB Output is correct
50 Correct 764 ms 32180 KB Output is correct
51 Correct 9 ms 9728 KB Output is correct
52 Correct 533 ms 22380 KB Output is correct
53 Correct 580 ms 22460 KB Output is correct
54 Correct 566 ms 22456 KB Output is correct
55 Correct 592 ms 22380 KB Output is correct
56 Correct 610 ms 22380 KB Output is correct
57 Correct 551 ms 22380 KB Output is correct
58 Correct 546 ms 24180 KB Output is correct
59 Correct 485 ms 23928 KB Output is correct
60 Correct 590 ms 23672 KB Output is correct
61 Correct 651 ms 23572 KB Output is correct
62 Correct 250 ms 31868 KB Output is correct
63 Correct 252 ms 31864 KB Output is correct
64 Correct 258 ms 32248 KB Output is correct
65 Correct 244 ms 31864 KB Output is correct
66 Correct 385 ms 27184 KB Output is correct
67 Correct 371 ms 26928 KB Output is correct
68 Correct 393 ms 27076 KB Output is correct
69 Correct 385 ms 26928 KB Output is correct
70 Correct 396 ms 27056 KB Output is correct
71 Correct 390 ms 26928 KB Output is correct
72 Correct 411 ms 26904 KB Output is correct
73 Correct 388 ms 26416 KB Output is correct
74 Correct 393 ms 26928 KB Output is correct
75 Correct 437 ms 26980 KB Output is correct
76 Correct 732 ms 27120 KB Output is correct
77 Correct 692 ms 26064 KB Output is correct
78 Correct 753 ms 28920 KB Output is correct
79 Correct 741 ms 27632 KB Output is correct
80 Correct 752 ms 31856 KB Output is correct
81 Correct 744 ms 29800 KB Output is correct
82 Correct 735 ms 29940 KB Output is correct
83 Correct 742 ms 27896 KB Output is correct
84 Correct 750 ms 31728 KB Output is correct
85 Correct 759 ms 30644 KB Output is correct
86 Correct 751 ms 27632 KB Output is correct
87 Correct 745 ms 28660 KB Output is correct
88 Correct 617 ms 28784 KB Output is correct
89 Correct 609 ms 26356 KB Output is correct
90 Correct 620 ms 26548 KB Output is correct
91 Correct 629 ms 27632 KB Output is correct
92 Correct 614 ms 26804 KB Output is correct
93 Correct 616 ms 26612 KB Output is correct
94 Correct 623 ms 26352 KB Output is correct
95 Correct 619 ms 27248 KB Output is correct
96 Correct 607 ms 26512 KB Output is correct
97 Correct 615 ms 27632 KB Output is correct