Submission #972702

#TimeUsernameProblemLanguageResultExecution timeMemory
972702LCJLYMergers (JOI19_mergers)C++14
100 / 100
1665 ms183796 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<long long,long long>pii; typedef pair<int,pii>pi2; mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); int n,k; vector<int>adj[500005]; int two[22][500005]; int in[500005]; int out[500005]; int d[500005]; int ptr=0; void dfs(int index, int par){ in[index]=++ptr; for(int x=0;x<20;x++){ two[x+1][index]=two[x][two[x][index]]; } for(auto it:adj[index]){ if(it==par) continue; d[it]=d[index]+1; two[0][it]=index; dfs(it,index); } out[index]=ptr; } int lca(int a, int b){ if(d[a]>d[b]) swap(a,b); int diff=d[b]-d[a]; for(int x=0;x<20;x++){ if(diff&(1<<x)){ b=two[x][b]; } } if(a==b) return a; for(int x=19;x>=0;x--){ if(two[x][a]!=two[x][b]){ a=two[x][a]; b=two[x][b]; } } return two[0][a]; } struct DSU{ vector<int>e; void init(int n){ e=vector<int>(n,-1); } int get(int x){return e[x]<0?x:e[x]=get(e[x]);} bool unite(int x, int y){ x=get(x); y=get(y); if(x==y) return 0; if(d[x]>d[y]) swap(x,y); e[x]+=e[y]; e[y]=x; return 1; } }; bool cmp(int a, int b){ return in[a]<in[b]; } DSU dsu; bool visited[500005]; int deg[500005]; void solve(){ cin >> n >> k; vector<pii>edge; int temp,temp2; for(int x=0;x<n-1;x++){ cin >> temp >> temp2; adj[temp].push_back(temp2); adj[temp2].push_back(temp); edge.push_back({temp,temp2}); } dfs(1,-1); vector<int>v[k+5]; for(int x=1;x<=n;x++){ cin >> temp; v[temp].push_back(x); } dsu.init(n+5); for(int x=1;x<=k;x++){ if((int)v[x].size()<=1) continue; //sort(v[x].begin(),v[x].end(),cmp); for(int y=0;y<(int)v[x].size();y++){ int hold=lca(v[x][y],v[x][0]); int cur=dsu.get(v[x][0]); while(d[cur]>d[hold]){ dsu.unite(cur,two[0][cur]); cur=dsu.get(cur); } cur=dsu.get(v[x][y]); while(d[cur]>d[hold]){ dsu.unite(cur,two[0][cur]); cur=dsu.get(cur); } } } int counter=0; for(int x=0;x<n-1;x++){ int a=edge[x].first; int b=edge[x].second; a=dsu.get(a); b=dsu.get(b); if(a==b) continue; deg[a]++; deg[b]++; } for(int x=1;x<=n;x++){ int hold=dsu.get(x); if(visited[hold]) continue; visited[hold]=true; if(deg[hold]==1) counter++; } cout << (counter+1)/2; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //freopen("in.txt","r",stdin); //cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...