Submission #526423

#	Time	Username	Problem	Language	Result	Execution time	Memory
526423		CPSC	Capital City (JOI20_capital_city)	C++14	41 / 100	3060 ms	47584 KiB

capital_city

# 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;
    par[c] = p;
    int x = col[c];
    queue <int> q;
    int ff = 0;
    for (int i = 0; i < vv[x].size(); i++) {
        int vert1 = vv[x][i];
        if (!now[vert1] | blocked[col[vert1]]) {
            ff = 1;
            break;
        }
         q.push(vv[x][i]);
         viss[x] = 1;
    }
    int pas = 0;
    vector <int> vvv;vvv.pb(x);
     if (!ff) {
        while (q.size()) {
            int vert = q.front();
            int parr = par[vert];
            if (!now[vert]) {
                ff = 1;break;
            }
            if (blocked[col[vert]]) {
                ff = 1;
                 break;
            }
            q.pop();
            if (parr == -1) continue;
            if (vert != c && par[vert] && !viss[col[parr]]) {
                pas++;
                 vvv.pb(col[parr]);
                for (int i = 0; i < vv[col[parr]].size(); i++) {
                    int vert1 = vv[col[parr]][i];
                    if (!now[vert1] || blocked[col[vert1]]) {
                        ff = 1;
                        break;
                    }
                     q.push(vert1);
                }if (ff) break;
                viss[col[parr]] = 1;
            }
        }
    }
    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);
    }
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    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 (stderr)

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:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < vv[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
capital_city.cpp:51:13: warning: suggest parentheses around operand of '!' or change '|' to '||' or '!' to '~' [-Wparentheses]
   51 |         if (!now[vert1] | blocked[col[vert1]]) {
      |             ^~~~~~~~~~~
capital_city.cpp:76:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                 for (int i = 0; i < vv[col[parr]].size(); i++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < vvv.size(); i++) viss[vvv[i]] = 0;
      |                     ~~^~~~~~~~~~~~
capital_city.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < v[c].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
capital_city.cpp: At global scope:
capital_city.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main() {
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 59