Submission #1205175

#TimeUsernameProblemLanguageResultExecution timeMemory
1205175mychecksedadCapital City (JOI20_capital_city)C++20
100 / 100
386 ms76536 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, col[N], D = 0, k, s[N], ans, col_cnt[N], id[N], par[N], in_queue[N]; vi g[N], C[N]; bitset<N> vis = 0, used = 0; void pre(int v, int p){ id[v] = D; s[v] = 1; col_cnt[col[v]] = 0; in_queue[col[v]] = -1; for(int u: g[v]){ if(u != p && !vis[u]){ pre(u, v); s[v] += s[u]; } } } void dfs(int v, int p){ col_cnt[col[v]]++; used[v] = 0; for(int u: g[v]){ if(u != p && !vis[u]){ par[u] = v; dfs(u, v); } } } int num; int centro(int v, int p){ for(int u: g[v]){ if(u == p || vis[u]) continue; if(s[u] >= (num+1)/2) return centro(u, v); } return v; } void f(int v){ ++D; pre(v, v); num = s[v]; v = centro(v, v); dfs(v, v); bool ok = true; queue<int> q; q.push(col[v]); in_queue[col[v]] = 1; int res = 0; used[v] = 1; while(!q.empty() && ok){ ++res; int c = q.front(); q.pop(); for(int u: C[c]){ if(id[u] != D){ ok = false; break; } while(u != v && !used[u]){ used[u] = 1; if(in_queue[col[u]] == -1){ q.push(col[u]); in_queue[col[u]] = 1; } u = par[u]; } } } if(ok){ ans = min(ans, res); } vis[v] = 1; for(int u: g[v]){ if(!vis[u]) f(u); } } void solve(){ cin >> n >> k; for(int i = 1; i < n; ++i){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } for(int i = 1; i <= n; ++i){ int c; cin >> c; C[c].pb(i); col[i] = c; } ans = k; f(1); cout << ans - 1; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...