제출 #99721

#제출 시각아이디문제언어결과실행 시간메모리
99721cki86201Unique Cities (JOI19_ho_t5)C++11
32 / 100
680 ms38676 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]; void pdfs(int x, int fa) { mxdep[x] = dep[x]; for(int e : E[x]) if(e != fa) { dep[e] = dep[x] + 1; pdfs(e, x); mxdep[x] = max(mxdep[x], mxdep[e]); } } void DFS(int x, int fa, int T[], int min_uni) { pii mxx[2] = {}; rep(u, 2) mxx[u] = pii((int)-1e9, -1); for(int e : E[x]) if(e != fa) { int L = mxdep[e] - dep[x]; if(mxx[0].Fi < L) mxx[1] = mxx[0], mxx[0] = pii(L, e); else if(mxx[1].Fi < L) mxx[1] = pii(L, e); } for(int e : E[x]) if(e != fa) { int nu = min_uni; int g = -1; if(mxx[0].Se != e) g = mxx[0].Fi; else g = mxx[1].Fi; if(g >= 1 && min_uni >= dep[x] - g) nu = dep[x]; int L1 = mxdep[e] - dep[e]; int L2 = dep[e] - nu; if(L1 < L2) T[e] = 1; DFS(e, x, T, nu); } } int C[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}) { dep[rt] = 0; pdfs(rt, -1); DFS(rt, -1, X[tt], 0); ++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; }

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

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:87: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:89: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:92: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...