Submission #99737

#TimeUsernameProblemLanguageResultExecution timeMemory
99737cki86201Unique Cities (JOI19_ho_t5)C++11
32 / 100
1626 ms72356 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_set> #include <bitset> #include <time.h> #include <limits.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define all(x) x.begin(),x.end() typedef tuple<int, int, int> t3; int N, M; vector <int> E[200020]; int dis[2][200020]; int far(int t, int x) { vector <int> q; q.pb(x); for(int i=1;i<=N;i++) dis[t][i] = -1; dis[t][x] = 0; rep(i, szz(q)) { int a = q[i]; for(int e : E[a]) if(dis[t][e] == -1) { dis[t][e] = dis[t][a] + 1; q.pb(e); } } return q.back(); } int ans[200020]; int dep[200020], mxdep[200020]; int ST[200020], EN[200020], cs, rev[200020]; int par[200020]; int Q[200020]; int nxt[200020][20]; void pdfs(int x, int fa) { mxdep[x] = dep[x]; ST[x] = ++cs; rev[cs] = x; int mxl[2] = {}; for(int e : E[x]) if(e != fa) { dep[e] = dep[x] + 1; par[e] = x; pdfs(e, x); if(mxdep[x] < mxdep[e]) mxdep[x] = mxdep[e], nxt[x][0] = e; int L = mxdep[e] - dep[x]; if(mxl[0] < L) mxl[1] = mxl[0], mxl[0] = L; else if(mxl[1] < L) mxl[1] = L; } int len = mxl[1]; if(len) { int t = x; rep(j, len) Q[t] = 1, t = par[t]; } EN[x] = cs; } int get_nxt(int x, int p) { rep(i, 20) if(1<<i & p) x = nxt[x][i]; return x; } int C[200020]; vector <int> H[200020]; int cnt[200020]; int main() { scanf("%d%d", &N, &M); for(int i=1;i<N;i++) { int x, y; scanf("%d%d", &x, &y); E[x].pb(y); E[y].pb(x); } for(int i=1;i<=M;i++) scanf("%d", C + i); int a = far(0, 1); int b = far(0, a); far(1, b); int tt = 0; int X[2][200020] = {}; for(int rt : {a, b}) { cs = 0; for(int i=1;i<=N;i++) { Q[i] = 0; rep(j, 20) nxt[i][j] = 0; H[i].clear(); } dep[rt] = 0; pdfs(rt, -1); for(int j=1;j<20;j++) { for(int i=1;i<=N;i++) nxt[i][j] = nxt[ nxt[i][j-1] ][j-1]; } for(int i=1;i<=N;i++) if(Q[i] == 0 && i != rt) { int L = mxdep[i] - dep[i]; int ni = get_nxt(i, (L + 1) / 2); H[ST[ni]].pb(C[par[i]]); H[EN[ni]+1].pb(-C[par[i]]); } for(int i=1;i<=M;i++) cnt[i] = 0; int res = 0; for(int i=1;i<=N;i++) { for(int e : H[i]) { if(e > 0) res += (cnt[e] == 0), ++cnt[e]; else res -= (cnt[-e] == 1), --cnt[-e]; } X[tt][rev[i]] = res; } ++tt; } for(int i=1;i<=N;i++) { if(dis[0][i] >= dis[1][i]) ans[i] = X[0][i]; else ans[i] = X[1][i]; } for(int i=1;i<=N;i++) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:94:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=M;i++) scanf("%d", C + i);
                        ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...