Submission #241299

#	Time	Username	Problem	Language	Result	Execution time	Memory
241299		Mercenary	Capital City (JOI20_capital_city)	C++14	100 / 100	890 ms	46888 KiB

capital_city

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 10;
int n , k;
int c[maxn] , cnt_col[maxn];
vector<int> col_node[maxn];
vector<int> adj[maxn];
int sub[maxn],big[maxn];
int vis[maxn];
int vis1[maxn];

int FindRoot(int u){
    function<void(int,int)> dfs = [&](int u , int v){
        sub[u] = 1;big[u] = -1;
        for(auto c : adj[u]){
            if(c != v && vis[c] == 0){
                dfs(c , u);
                sub[u] += sub[c];
                if(big[u] == -1 || sub[big[u]] < sub[c])big[u] = c;
            }
        }
    };
    dfs(u , 0);
    int tot = sub[u];
    while(big[u] != -1 && sub[big[u]] * 2 >= tot)u = big[u];
    return u;
}

int pa[maxn];
int res = 1e9;
bool vis_col[maxn];

void centroid(int u){
    u = FindRoot(u);
    int root = u;
    pa[u] = u;
    function<void(int,int)> dfs = [&](int u , int v){
        vis1[u] = root;
        for(auto c : adj[u]){
            if(c != v && vis[c] == 0){
                pa[c] = u;
                dfs(c , u);
            }
        }
    };
    dfs(u , 0);
    vector<int> ans;
    queue<int> q;q.push(u);
    int cnt = -1;
    bool ok = 1;
    while(q.size() && ok == 1){
        int u = q.front();q.pop();
        ++cnt;
        while(ok == 1){
            if(vis1[u] == 0)break;
            if(vis_col[c[u]] == 0){
                cnt -= cnt_col[c[u]];
                vis_col[c[u]] = 1;
                ans.pb(c[u]);
                for(auto &v : col_node[c[u]]){
                    q.push(v);
                    if(vis1[v] != root){
                        ok = 0;break;
                    }
                }
            }
            vis1[u] = 0;
            u = pa[u];
            if(u == root)break;
        }
    }
    for(auto c : ans){
        vis_col[c] = 0;
    }
    if(cnt == 0){
        res = min(res , (int)ans.size() - 1);
    }
    vis[u] = 1;
    for(auto c : adj[u]){
        if(vis[c] == 0)centroid(c);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> k;
    for(int i = 1 ; i < n ; ++i){
        int u , v;cin >> u >> v;
        adj[u].pb(v);adj[v].pb(u);
    }
    for(int i = 1 ; i <= n ; ++i){
        cin >> c[i];
        cnt_col[c[i]]++;
        col_node[c[i]].pb(i);
    }
    centroid(1);
    cout << res;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:104:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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