제출 #100925

#제출 시각아이디문제언어결과실행 시간메모리
100925Alexa2001Unique Cities (JOI19_ho_t5)C++17
64 / 100
895 ms36852 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 2e5 + 5; int down[Nmax], ans[Nmax], level[Nmax], st[Nmax], max_ex[Nmax]; bool ap[Nmax]; vector<int> v[Nmax]; int n, M, nr; int tip[Nmax], S[Nmax]; void read() { int i, x, y; cin >> n >> M; for(i=1; i<n; ++i) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } for(i=1; i<=n; ++i) cin >> tip[i]; } void print_sol() { int i; for(i=1; i<=n; ++i) cout << min(M, ans[i]) << '\n'; } void max_to(int &x, int y) { if(x < y) x = y; } void dfs0(int node, int dad = 0) { level[node] = level[dad] + 1; for(auto it : v[node]) if(it != dad) dfs0(it, node); } pair<int,int> diametru() { int i, A = 1, B = 1; dfs0(1); for(i=1; i<=n; ++i) if(level[i] > level[A]) A = i; dfs0(A); for(i=1; i<=n; ++i) if(level[i] > level[B]) B = i; return {A, B}; } void dfs(int node, int dad = 0) { down[node] = 1; level[node] = level[dad] + 1; for(auto it : v[node]) if(it != dad) { dfs(it, node); down[node] = max(down[node], down[it] + 1); } int i, mx = 0; for(i=0; i<v[node].size(); ++i) if(v[node][i] != dad) { max_ex[v[node][i]] = mx; max_to(mx, down[v[node][i]]); } mx = 0; for(i=v[node].size()-1; i>=0; --i) if(v[node][i] != dad) { max_to(max_ex[v[node][i]], mx); max_to(mx, down[v[node][i]]); } } int cnt_dist(vector<int> &v) { for(auto it : v) ap[tip[it]] = 1; int i, ans = 0; for(i=1; i<=M; ++i) if(ap[i]) { ++ans; ap[i] = 0; } return ans; } int bs(int val) { int st = 1, dr = nr, mid; while(st <= dr) { mid = (st + dr) / 2; if(level[S[mid]] <= val) st = mid + 1; else dr = mid - 1; } return dr; } void solve(int node, int dad = 0) { /* vector<int> see; for(i=0; i<stramos.size(); ++i) if(level[stramos[i]] <= level[node] - down[node]) see.push_back(stramos[i]); */ max_to(ans[node], bs(level[node] - down[node])); for(auto it : v[node]) if(it != dad) { /* vector<int> act = stramos; while(act.size() && level[act.back()] >= level[node] - max_ex[it]) act.pop_back(); act.push_back(node); */ int pos, val, lnr; pos = bs(level[node] - max_ex[it] - 1); lnr = nr; val = S[pos+1]; S[pos+1] = node; nr = pos+1; solve(it, node); S[pos+1] = val; nr = lnr; } } void Solve(int node) { dfs(node); int i; for(i=0; i<=nr; ++i) S[i] = 0; nr = 0; solve(node); } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); read(); auto P = diametru(); Solve(P.first); Solve(P.second); print_sol(); return 0; }

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

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++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...