제출 #905167

#제출 시각아이디문제언어결과실행 시간메모리
905167jay_jayjayUnique Cities (JOI19_ho_t5)C++17
4 / 100
2047 ms66992 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define all(x) (x).begin(),(x).end() int main() { int n,m;scanf("%d%d",&n,&m); vector<vector<int>> adj(n); for(int i=1;i<n;i++) { int u,v;scanf("%d%d",&u,&v);u--;v--; adj[u].push_back(v); adj[v].push_back(u); } vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--; // ;-; vector<int> sz(n),dep(n),mxdep(n),val(n); auto dfs1 = [&](auto self, int v, int p=-1, int rk=0) -> void { sz[v]=1; dep[v]=rk; mxdep[v]=0; for(auto x:adj[v]) if(x!=p) self(self,x,v,rk+1), sz[v]+=sz[x], mxdep[v]=max(mxdep[v],mxdep[x]+1); }; vector<int> S(m); int cnt=0; auto add = [&](int x, int d) { // printf("\t\tadd %d %d\n",x,d); cnt-=S[x]>0; S[x]+=d; cnt+=S[x]>0; }; vector<int> A; vector<array<int,2>> B; auto dfs2 = [&](auto self, int v, int p=-1) -> void { sort(all(adj[v]), [&](int a, int b) { return mxdep[a] > mxdep[b]; }); assert(p == -1 || adj[v][0] == p); if(p==-1) adj[v].insert(adj[v].begin(),-1); // printf("%d: ", v); // for(auto x:A)printf("%d ",x); // printf("\n"); // for(auto x:B)printf("%d|%d ", x[0],x[1]); // printf("\n"); vector<array<int,2>> R; for(int i=1;i<adj[v].size();i++) { int x = adj[v][i]; int d=0; if(i > 1) d=mxdep[adj[v][1]]+1; else if(adj[v].size() > 2) d=mxdep[adj[v][2]]+1; // printf("\t\t\tv=%d x=%d d=%d\n",v,x,d); // printf("\t\t\tcut %d\n", dep[v]-d); while(B.size() && B.back()[0] >= dep[v] - d) { R.push_back(B.back()); add(B.back()[1], -1); B.pop_back(); } B.push_back({dep[v], c[v]}); add(c[v],1); A.push_back(d); self(self, x, v); A.pop_back(); B.pop_back(); add(c[v],-1); } if(adj[v].size()>1) { int d=mxdep[adj[v][1]]+1; // printf("\t\t\texit d=%d\n", adj[v][1]); while(B.size() && B.back()[0] >= dep[v] - d) { R.push_back(B.back()); add(B.back()[1], -1); B.pop_back(); } } // printf("%d exit: ", v); // for(auto x:A)printf("%d ",x); // printf("(%d)\n", adj[v].size()>1?adj[v][1]:0); // for(auto x:B)printf("%d|%d ", x[0],x[1]); // printf("\n"); // for(int i=0;i<m;i++)printf("%d ",S[i]); // printf("\n"); val[v] = max(val[v],cnt); while(R.size()) { B.push_back(R.back()); add(B.back()[1], 1); R.pop_back(); } if(p==-1)adj[v].erase(adj[v].begin()); }; // find dia dfs1(dfs1, 0); int v1 = max_element(all(dep)) - dep.begin(); dfs1(dfs1, v1); int v2 = max_element(all(dep)) - dep.begin(); // printf("dia is %d, %d\n", v1, v2); dfs2(dfs2,v1); dfs1(dfs1,v2); dfs2(dfs2,v2); for(int i=0;i<n;i++)printf("%d ",val[i]); printf("\n"); }

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

joi2019_ho_t5.cpp: In instantiation of 'main()::<lambda(auto:24, int, int)> [with auto:24 = main()::<lambda(auto:24, int, int)>]':
joi2019_ho_t5.cpp:108:21:   required from here
joi2019_ho_t5.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int i=1;i<adj[v].size();i++) {
      |                             ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:10:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         int n,m;scanf("%d%d",&n,&m);
      |                 ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 int u,v;scanf("%d%d",&u,&v);u--;v--;
      |                         ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:18:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--;
      |                                       ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...