Submission #1108399

#TimeUsernameProblemLanguageResultExecution timeMemory
1108399salmonUnique Cities (JOI19_ho_t5)C++14
4 / 100
2085 ms77420 KiB
#include <bits/stdc++.h> using namespace std; int N; int M; vector<int> adjlst[200100]; int u,v; int parent[200100]; int lst[200100]; int d1,d2; bool diam[200100]; int d[200100]; int md[200100]; int pre[200100]; vector<int> path[200100]; int h; long long int ans[200100]; int c; int num; vector<pair<int,int>> uni; map<int,int> tooken; //3Na 3Si 3Al 12O void dfs(int i, int p, int de){ d[i] = de; md[i] = de; parent[i] = p; for(int j : adjlst[i]){ if(j == p) continue; dfs(j, i, de + 1); md[i] = max(md[i],md[j]); } } void solve(int i, int pa); void recurse(int i, int j, int pa){ uni.push_back({d[i],i}); auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1) ); vector<int> undo; int pa1 = d[i] + 1 - (md[j] - d[i] - 1); while(it != uni.end() && it -> first < pa1){ undo.push_back(lst[it -> second]); tooken[lst[it -> second]]++; advance(it,1); } solve(j,max(pa1,pa)); uni.pop_back(); reverse(undo.begin(),undo.end()); for(int i : undo){ tooken[i]--; if(tooken[i] == 0) tooken.erase(i); } } void solve(int i, int pa){//printf("i: %d\n",i); if(d[i] <= d[c]){ int child = -1; for(int j : path[i]){ if(j != parent[i]) child = j; } int num1 = d[i]; for(int j : adjlst[i]){ if(j == child || j == parent[i]) continue; num1 = max(num1,md[j]); } while(!uni.empty() && uni.back().first >= d[i] - (num1 - d[i]) ){ uni.pop_back(); } uni.push_back({d[i],i}); if(d[i] == d[c]){ int h = d[i] + 1 - (num - d[i] - 1); int it = 0; while(it != uni.size() && uni[it].first < h){ tooken[lst[uni[it].second]]++; it++; } solve(child,h); } else solve(child,2); } else{ /*if(i == 0){ for(pair<int,int> ii : tooken){ printf("t %d %d\n",ii.first,ii.second); } }*/ map<int,int,greater<int>> mep; for(int j : adjlst[i]){ if(j == parent[i]) continue; mep[md[j]]++; } ans[i] = tooken.size(); if(mep.empty()) return; if(mep.begin() -> second == 1){ int special; for(int j : adjlst[i]){ if(j == parent[i]) continue; if(md[i] == md[j]) special = j; } auto it1 = mep.begin(); advance(it1,1); int num; vector<int> undo1; if(it1 != mep.end()){ num = d[i] - (it1 -> first - d[i]); while(!uni.empty() && uni.back().first >= num){ if(uni.back().first < pa){ tooken[uni.back().second]--; if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second); } undo1.push_back(uni.back().second); uni.pop_back(); } } uni.push_back({d[i],i}); auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1)); vector<int> undo; int pa1 = d[i] + 1 - (md[special] - d[i] - 1); //printf("%d\n",uni.back().first); while(it != uni.end() && it -> first < pa1){ undo.push_back(lst[it -> second]); tooken[lst[it -> second]]++; advance(it,1); } solve(special,max(pa,pa1)); uni.pop_back(); reverse(undo.begin(),undo.end()); for(int i : undo){ tooken[i]--; if(tooken[i] == 0) tooken.erase(i); } while(!uni.empty() && uni.back().first >= d[i] - (md[i] - d[i])){ if(uni.back().first < pa){ tooken[uni.back().second]--; if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second); } undo1.push_back(uni.back().second); uni.pop_back(); } for(int j : adjlst[i]){ if(j == parent[i]) continue; if(md[j] == md[i]) continue; recurse(i,j,pa); } reverse(undo1.begin(),undo1.end()); for(int i : undo1){ uni.push_back({d[i],i}); if(uni.back().first < pa){ tooken[uni.back().second]++; } } } else{ vector<int> undo1; int num = d[i] - (md[i] - d[i]); while(!uni.empty() && uni.back().first >= num){ if(uni.back().first < pa){ tooken[uni.back().second]--; if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second); } undo1.push_back(uni.back().second); uni.pop_back(); } for(int j : adjlst[i]){ if(j == parent[i]) continue; recurse(i,j,pa); } reverse(undo1.begin(),undo1.end()); for(int i : undo1){ uni.push_back({d[i],i}); if(uni.back().first < pa){ tooken[uni.back().second]++; } } } } } int main(){ scanf(" %d",&N); scanf(" %d",&M); for(int i = 0; i < N - 1; i++){ scanf(" %d",&u); scanf(" %d",&v); u--; v--; adjlst[u].push_back(v); adjlst[v].push_back(u); } for(int i = 0; i < N; i++){ scanf(" %d",&lst[i]); lst[i]--; } dfs(1,-1,0); pair<int,int> ii = {0,-1}; for(int i = 0; i < N; i++){ ii = max(ii, {d[i],i}); ans[i] = 0; } d1 = ii.second; dfs(d1,-1,0); ii = {0,-1}; for(int i = 0; i < N; i++){ ii = max(ii, {d[i],i}); } d2 = ii.second; num = ii.first; h = d2; for(int i = 0; i < num; i++){ path[h].push_back(parent[h]); path[parent[h]].push_back(h); h = parent[h]; } if(num % 2 == 1){ //printf("%d %d\n",d1,d2); c = d2; for(int i = 0; i < num / 2 + 1; i++){ c = parent[c]; } solve(d1,0); //printf("S"); dfs(d2,-1,0); c = d1; for(int i = 0; i < num / 2 + 1; i++){ c = parent[c]; } uni.clear(); tooken.clear(); solve(d2,0); //printf("S\n\n"); } else{ //printf("%d %d\n",d1,d2); c = d2; for(int i = 0; i < num / 2 + 1; i++){ c = parent[c]; } solve(d1,0); //printf("S"); dfs(d2,-1,0); c = d1; for(int i = 0; i < num/2 + 1; i++){ c = parent[c]; } uni.clear(); tooken.clear(); solve(d2,0); //printf("S\n\n"); } for(int i = 0; i < N; i++){ printf("%d\n",ans[i]); } } /* 6 4 6 1 1 2 2 3 3 4 3 5 1 2 1 2 4 4 4 4 1 2 1 3 1 4 1 2 3 4 7 7 1 2 1 3 1 4 2 5 3 6 4 7 1 2 3 4 5 6 7 5 1 2 1 3 1 4 1 5 3 1 1 1 1 1 */

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while(it != uni.size() && uni[it].first < h){
      |                   ~~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:306:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  306 |         printf("%d\n",ans[i]);
      |                 ~^    ~~~~~~
      |                  |         |
      |                  int       long long int
      |                 %lld
joi2019_ho_t5.cpp:213:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:218:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:227:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:149:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  149 |             solve(special,max(pa,pa1));
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...