oj.uz

Submission #526413

# Submission time Handle Problem Language Result Execution time Memory
526413 2022-02-14T17:42:47 Z CPSC Capital City (JOI20_capital_city) C++14
1 / 100
 2171 ms 47768 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int  sz[N],par[N],col[N],viss[N],blocked[N],now[N],vis[N],ans,n,k,a,b;
vector <int> v[N],vv[N];
void dfs(int a, int p) {
    if (vis[a]) return ;
    sz[a] = 1;
    par[a] = p;
    now[a] = 1;
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        //cout<<a<<"          "<<to<<endl;
        if (to == p || vis[to]) continue;
        dfs(to,a);
        sz[a] += sz[to];
    }
}
int find_centroid(int a, int p, int raod) {
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (vis[to] || to == p) continue;
        if (sz[to] > raod/2) return find_centroid(to,a,raod);
    }
    return a;
}
void init(int a, int p) {
    if (vis[a]) return;
    now[a] = 0;
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p || vis[to]) continue;
         init(to,a);
    }
}
void init_centroid(int a, int p){ 
    dfs(a,p);

    int c = find_centroid(a, p ,sz[a]); 
    dfs(c,p);
    vis[c] = 1;    //cout<<c<<endl;
    par[c] = p;
    int x = col[c];
    queue <int> q;
    for (int i = 0; i < vv[x].size(); i++) {
         q.push(vv[x][i]);
         viss[x] = 1;
    }
    int pas = 0;
    int ff = 0;

    vector <int> vvv;
    vvv.pb(x);
    //cout<<q.size()<<endl;
    //cout<<c<<"centroid"<<endl;
    while (q.size()) {
        int vert = q.front();
        int parr = par[vert];
      //  cout<<vert<<"  ";
        //cout<<vert<<"  ";
        if (!now[vert]) {
            ff = 1;break;
        }
        if (blocked[col[vert]]) {
            ff = 1;
             break;
        }
        q.pop();
        if (parr == -1) continue;
        if (par[vert] && !viss[col[parr]]) {
        //    cout<<vert<<" "<<col[parr]<<endl;
            pas++;
             vvv.pb(col[parr]);
            for (int i = 0; i < vv[col[parr]].size(); i++) {
                int vert1 = vv[col[parr]][i];
                 q.push(vert1);
            }
            viss[col[parr]] = 1;
        }
    }//cout<<endl<<endl;
    if (!ff) {
        ans = min(ans, pas);
    }
    for (int i = 0; i < vvv.size(); i++) viss[vvv[i]] = 0;
    init(a,p);
    blocked[col[c]] = 1;
    vis[c] = 1;
    
    for (int i = 0; i < v[c].size(); i++) {
        if(!vis[v[c][i]]) init_centroid(v[c][i],c);
    }
}
signed main() {
    cin>>n>>k;
    ans = 1e9;
    for (int i = 1; i <= n - 1; i++) {
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    for (int i = 1; i <= n; i++) {
        cin>>col[i];
        vv[col[i]].pb(i);
    } //cout<<endl<<endl;
    init_centroid(1,-1);
    cout<<ans<<endl;
}

Compilation message

capital_city.cpp: In function 'void dfs(int, int)':
capital_city.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
capital_city.cpp: In function 'int find_centroid(int, int, int)':
capital_city.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
capital_city.cpp: In function 'void init(int, int)':
capital_city.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
capital_city.cpp: In function 'void init_centroid(int, int)':
capital_city.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < vv[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
capital_city.cpp:77:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for (int i = 0; i < vv[col[parr]].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < vvv.size(); i++) viss[vvv[i]] = 0;
      |                     ~~^~~~~~~~~~~~
capital_city.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < v[c].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14332 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14384 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14352 KB Output is correct
9 Correct 8 ms 14392 KB Output is correct
10 Correct 8 ms 14408 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14332 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14384 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14352 KB Output is correct
9 Correct 8 ms 14392 KB Output is correct
10 Correct 8 ms 14408 KB Output is correct
11 Correct 13 ms 14536 KB Output is correct
12 Correct 12 ms 14540 KB Output is correct
13 Correct 14 ms 14536 KB Output is correct
14 Correct 11 ms 14548 KB Output is correct
15 Incorrect 10 ms 14540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 47324 KB Output is correct
2 Correct 399 ms 47768 KB Output is correct
3 Correct 650 ms 47112 KB Output is correct
4 Correct 329 ms 47752 KB Output is correct
5 Incorrect 2171 ms 44732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14332 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 7 ms 14384 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14352 KB Output is correct
9 Correct 8 ms 14392 KB Output is correct
10 Correct 8 ms 14408 KB Output is correct
11 Correct 13 ms 14536 KB Output is correct
12 Correct 12 ms 14540 KB Output is correct
13 Correct 14 ms 14536 KB Output is correct
14 Correct 11 ms 14548 KB Output is correct
15 Incorrect 10 ms 14540 KB Output isn't correct
16 Halted 0 ms 0 KB -