제출 #773518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773518		1bin	Unique Cities (JOI19_ho_t5)	C++14	4 / 100	2073 ms	178672 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, C[NMAX], D[NMAX], a, b, mxd, ix, r1, r2, ans[NMAX], cur, cnt[NMAX];
vector<int> adj[NMAX];
vector<pair<int, int>> v[NMAX];

void dfs2(int x, int p, int d){
    if(d > mxd) mxd = d, ix = x;
    for(int&nx : adj[x])
        if(nx != p) dfs2(nx, x, d + 1);
    return;
}

void go(int x, int p){
    v[x].clear();
    for(int& nx : adj[x])
        if(nx != p){
            go(nx, x);
            v[x].emplace_back(v[nx][0].first + 1, nx);
        }
    v[x].emplace_back(0, x);
    sort(all(v[x])); reverse(all(v[x]));
    return;
}

void f(int x, int add){
    if(add){
        if(++cnt[C[x]] == 1) cur++;
    }
    else{
        if(--cnt[C[x]] == 0) cur--;
    }
    return;
}

stack<int> st;
void dfs(int x, int p, int d){
    stack<int> t;
    D[d] = x;
    for(int i = 0; i < v[x].size(); i++){
        int nx = v[x][i].second;
        int mxd = n + 1;
        if(i) mxd = d - v[x][0].first;
        else if(v[x].size() > 2) mxd = d - v[x][1].first;
        
        while(st.size() && st.top() >= mxd){
            f(D[st.top()], 0);
            t.emplace(st.top()); st.pop();
        }
        if(nx == x) ans[x] = max(ans[x], cur);
        else {
            st.emplace(d); f(x, 1);
            dfs(nx, x, d + 1);
            st.pop(); f(x, 0);
        }
    }
    
    while(t.size()){
        f(D[t.top()], 1);
        st.emplace(t.top()); t.pop();
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }    
    for(int i = 1; i <= n; i++) cin >> C[i];
    dfs2(1, -1, 0);
    r1 = ix;
    mxd = 0; dfs2(r1, -1, 0);
    r2 = ix;
    
    go(r1, -1); dfs(r1, -1, 0);
    go(r2, -1); dfs(r2, -1, 0);
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}

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

joi2019_ho_t5.cpp: In function 'void dfs(int, int, int)':
joi2019_ho_t5.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < v[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32