Submission #526420

#	Time	Username	Problem	Language	Result	Execution time	Memory
526420		CPSC	Capital City (JOI20_capital_city)	C++14	11 / 100	3084 ms	44356 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;
    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];
        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: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:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int i = 0; i < vv[col[parr]].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < vvv.size(); i++) viss[vvv[i]] = 0;
      |                     ~~^~~~~~~~~~~~
capital_city.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < v[c].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
capital_city.cpp: At global scope:
capital_city.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main() {
      | ^~~~

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