제출 #205100

#제출 시각아이디문제언어결과실행 시간메모리
205100achibasadzishviliMergers (JOI19_mergers)C++17
100 / 100
1982 ms232040 KiB
#include<bits/stdc++.h> #define ll int #define f first #define s second #define pb push_back using namespace std; ll P[500002][20],lvl[500002],pp[500002],in[500002],out[500002],timer,ch[500002]; ll n,k,bst[500002],c[500002],par[500002],p[500002],sz[500002],raod[500002]; ll fix[500002]; set<ll>st[500002]; vector<ll>v[500002],del[500002],fer[500002]; void dfs(ll x,ll par) { P[x][0]=par; pp[x] = par; for (int i=1;i<=19;i++) P[x][i]=P[P[x][i-1]][i-1]; timer++; in[x]=timer; ch[x] = 1; for (int i=0;i<v[x].size();i++) if (v[x][i] != par) { lvl[v[x][i]]=lvl[x]+1; dfs(v[x][i],x); ch[x] += ch[v[x][i]]; } out[x]=timer; } ll lca(ll a,ll b) { if(lvl[a] > lvl[b])swap(a,b); if (in[a] <= in[b] && out[b] <= out[a]) return a; for (int i=19;i>=0;i--) if (P[a][i]) if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]])) a=P[a][i]; return P[a][0]; } ll find(ll x){ if(p[x] == x)return x; return p[x] = find(p[x]); } void join(ll x,ll y){ //cout << x << " " << y << endl; x = find(x); y = find(y); if(x == y)return; if(sz[y] > sz[x])swap(x , y); sz[x] += sz[y]; p[y] = x; } void solve(ll x){ if(v[x].size() == 0){ bst[x] = x; if(par[c[x]] != x)st[x].insert(c[x]); return; } for(int i=0; i<v[x].size(); i++) solve(v[x][i]); bst[x] = bst[v[x][0]]; if(st[bst[x]].size() > 0){ join(c[x] , (*st[bst[x]].begin())); } st[bst[x]].insert(c[x]); for(int i=1; i<v[x].size(); i++){ ll t = bst[v[x][i]]; for(set<ll>::iterator it = st[t].begin(); it != st[t].end(); it++){ join(c[x] , (*it)); st[bst[x]].insert((*it)); } } for(int i=0; i<del[x].size(); i++) st[bst[x]].erase(st[bst[x]].find(del[x][i])); } int main(){ ios::sync_with_stdio(false); cin >> n >> k; for(int i=1; i<n; i++){ ll x,y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } for(int i=1; i<=n; i++){ cin >> c[i]; fer[c[i]].pb(i); } dfs(1 , 0); for(int i=1; i<=k; i++){ par[i] = fer[i][0]; for(int j=1; j<fer[i].size(); j++) par[i] = lca(par[i] , fer[i][j]); del[par[i]].pb(i);/* for(int j=0; j<fer[i].size(); j++){ ll x = fer[i][j]; while(1){ join(i , c[x]); if(x == par[i])break; x = pp[x]; } }*/ } for(int i=1; i<=n; i++){ sz[i] = 1; p[i] = i; v[i].clear(); } for(int i=2; i<=n; i++) v[pp[i]].pb(i); for(int i=1; i<=n; i++) for(int j=1; j<v[i].size(); j++) if(ch[v[i][j]] > ch[v[i][0]]) swap(v[i][j] , v[i][0]); solve(1); for(int i=1; i<=n; i++){ for(int j=0; j<v[i].size(); j++){ ll x = v[i][j]; if(find(c[i]) != find(c[x])){ raod[find(c[i])]++; raod[find(c[x])]++; } } } ll ans = 1; for(int i=1; i<=k; i++){ if(!fix[find(i)]){ fix[find(i)] = 1; if(raod[find(i)] == 1)ans++; } } cout << ans / 2 << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
mergers.cpp: In function 'void solve(int)':
mergers.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
mergers.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
mergers.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<del[x].size(); i++)
                  ~^~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<fer[i].size(); j++)
                      ~^~~~~~~~~~~~~~
mergers.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~
mergers.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++){
                      ~^~~~~~~~~~~~
#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...