oj.uz

Submission #1004836

# Submission time Handle Problem Language Result Execution time Memory
1004836 2024-06-21T18:39:02 Z Unforgettablepl Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 45172 KB 
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> adj[200001];
bool processed[200001];
int siz[200001];
bool current[200001];
int par[200001];
int visitedcol[200001];
int col[200001];
vector<int> nodes[200001];

void set_all(int x,int p,bool set_val){
    if(processed[x])return;
    current[x] = set_val;
    par[x] = p;
    for(int&i:adj[x])if(i!=p)set_all(i,x,set_val);
}

int centroid;

int centroidcalc(int x,int p,int tot){
    if(processed[x])return 0;
    siz[x] = 1;
    bool works = true;
    for(int&i:adj[x])if(i!=p)if(centroidcalc(i,x,tot)>tot/2)works=false;
    if(tot-siz[x]>tot/2)works=false;
    if(works){
        centroid = x;
        return 1e15;
    }
    return siz[x];
}

int calc(int x){
    centroidcalc(x,0,siz[x]);
    set_all(centroid,0,true); // Get them into processing stage
    queue<int> q; // Queue of colours
    q.emplace(col[centroid]);
    int ans = -1;
    bool works = true;
    while(!q.empty()){
        int curr = q.front();q.pop();
        if(visitedcol[curr]==centroid)continue;
        visitedcol[curr]=centroid;
        ans++;
        for(int&i:nodes[curr]){
            if(!current[i]){
                while(!q.empty())q.pop();
                ans = 1e15;
                break;
            }
            if(par[i])q.emplace(col[par[i]]);
        }
    }
    set_all(centroid,0,false);
    processed[centroid]=true;
    for(int&i:adj[centroid])if(!processed[i])ans=min(ans,calc(i));
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    for(int i=1;i<=n;i++){
        cin>>col[i];
        nodes[col[i]].emplace_back(i);
    }
    cout << calc(1) << '\n';
}

Compilation message

capital_city.cpp: In function 'long long int calc(long long int)':
capital_city.cpp:44:10: warning: unused variable 'works' [-Wunused-variable]
   44 |     bool works = true;
      |          ^~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14428 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 2 ms 14428 KB Output is correct
4 Correct 2 ms 14428 KB Output is correct
5 Correct 2 ms 14428 KB Output is correct
6 Correct 2 ms 14428 KB Output is correct
7 Correct 2 ms 14428 KB Output is correct
8 Correct 2 ms 14428 KB Output is correct
9 Correct 2 ms 14428 KB Output is correct
10 Correct 2 ms 14428 KB Output is correct
11 Correct 38 ms 15952 KB Output is correct
12 Correct 49 ms 15892 KB Output is correct
13 Correct 38 ms 15956 KB Output is correct
14 Correct 39 ms 16112 KB Output is correct
15 Correct 43 ms 15952 KB Output is correct
16 Correct 39 ms 15956 KB Output is correct
17 Correct 55 ms 16216 KB Output is correct
18 Correct 54 ms 16004 KB Output is correct
19 Correct 50 ms 16172 KB Output is correct
20 Correct 50 ms 16212 KB Output is correct
21 Correct 51 ms 16072 KB Output is correct
22 Correct 50 ms 15980 KB Output is correct
23 Correct 75 ms 15952 KB Output is correct
24 Correct 48 ms 15956 KB Output is correct
25 Correct 60 ms 15952 KB Output is correct
26 Correct 57 ms 15956 KB Output is correct
27 Correct 57 ms 16092 KB Output is correct
28 Correct 58 ms 15952 KB Output is correct
29 Correct 56 ms 15952 KB Output is correct
30 Correct 53 ms 16056 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 45172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14428 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 2 ms 14428 KB Output is correct
4 Correct 2 ms 14428 KB Output is correct
5 Correct 2 ms 14428 KB Output is correct
6 Correct 2 ms 14428 KB Output is correct
7 Correct 2 ms 14428 KB Output is correct
8 Correct 2 ms 14428 KB Output is correct
9 Correct 2 ms 14428 KB Output is correct
10 Correct 2 ms 14428 KB Output is correct
11 Correct 38 ms 15952 KB Output is correct
12 Correct 49 ms 15892 KB Output is correct
13 Correct 38 ms 15956 KB Output is correct
14 Correct 39 ms 16112 KB Output is correct
15 Correct 43 ms 15952 KB Output is correct
16 Correct 39 ms 15956 KB Output is correct
17 Correct 55 ms 16216 KB Output is correct
18 Correct 54 ms 16004 KB Output is correct
19 Correct 50 ms 16172 KB Output is correct
20 Correct 50 ms 16212 KB Output is correct
21 Correct 51 ms 16072 KB Output is correct
22 Correct 50 ms 15980 KB Output is correct
23 Correct 75 ms 15952 KB Output is correct
24 Correct 48 ms 15956 KB Output is correct
25 Correct 60 ms 15952 KB Output is correct
26 Correct 57 ms 15956 KB Output is correct
27 Correct 57 ms 16092 KB Output is correct
28 Correct 58 ms 15952 KB Output is correct
29 Correct 56 ms 15952 KB Output is correct
30 Correct 53 ms 16056 KB Output is correct
31 Execution timed out 3053 ms 45172 KB Time limit exceeded
32 Halted 0 ms 0 KB -