제출 #100924

#제출 시각아이디문제언어결과실행 시간메모리
100924Alexa2001Unique Cities (JOI19_ho_t5)C++17
4 / 100
2051 ms275456 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; int tip[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 << 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; } void solve(int node, vector<int> &stramos, int dad = 0) { int i; 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], cnt_dist(see)); //stramos.push_back(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); solve(it, act, node); } } void Solve(int node) { dfs(node); vector<int> V; solve(node, V); } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); read(); // dfs(1); 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)
              ~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, std::vector<int>&, int)':
joi2019_ho_t5.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<stramos.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...