제출 #1068051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068051		_8_8_	Unique Cities (JOI19_ho_t5)	C++17	0 / 100	112 ms	35508 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

int n,m,c[N],d1,d2;
vector<int> g[N];
int f(int v) {
    queue<int> q;
    vector<bool> vis(n + 1,0);
    q.push(v);
    vis[v] = 1;
    int ret;
    while(!q.empty()) {
        int u = q.front();
        ret = u;
        q.pop();
        for(int to:g[u]) {
            if(!vis[to]) {
                q.push(to);
                vis[to] = 1;
            }
        }
    }
    return ret;
}
int dp[N];
void solve(int x,int y) {
    vector<bool> ok(n + 1,0);
    vector<int> dep(n+1,0),path,di(n + 1,0),col(n + 1,0);
    function<void(int,int)> prec = [&](int v,int pr){
        for(int to:g[v]) {
            if(to == pr) continue;
            dep[to] = dep[v] + 1;
            prec(to,v);
            ok[v] = (ok[v] | ok[to]);
        }
        if(v == y) {
            ok[v] = 1;
        }
        if(ok[v]) {
            path.push_back(v);
        }
    };
    dep[x] = 1;
    prec(x,-1);
    queue<int> q;
    di[y] = 1;
    q.push(y);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        col[di[v]]++;
        for(int to:g[v]) {
            if(!di[to]) {
                di[to] = di[v] + 1;
                q.push(to);
            }
        }
    }
    set<int> d;
    for(int i = 1;i <= n;i++) {
        if(i != y && col[di[i]] == 1) {
            d.insert(dep[i]);
        }
    }
    int cur = 0;
    for(int i = 0;i < (int)path.size();i++) {
        assert(cur == dep[y] - dep[path[i]]);
        int v = path[i];
        while(!d.empty()) {
            int val = dep[v] - (*d.rbegin());
            if(val <= cur) {
                d.erase(*d.rbegin());
            } else break;
        }
        if((int)d.size()) dp[v] = (int)d.size();
        cur++;
    }
}
bool is[N],l[N];
void go(int v,int pr = -1) {
    l[v] = 1;
    for(int to:g[v]) {
        if(to == pr) continue;
        l[v] = false;
        go(to,v);
        is[v] = (is[v] | is[to]);
    }
    if(v == d2) {
        is[v] = 1;
    }
}
void dfs(int v,int pr = -1) {
    for(int to:g[v]) {
        if(to == pr) continue;
        if(!is[to]) dp[to] = dp[v] + (l[to]);
        dfs(to,v);
    }
}
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    d1 = f(1),d2 = f(d1);
    solve(d1,d2);
    solve(d2,d1);
    go(d1);
    dfs(d1);
    for(int i = 1;i <= n;i++) {
        cout << dp[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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

joi2019_ho_t5.cpp: In function 'int f(int)':
joi2019_ho_t5.cpp:27:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     return ret;
      |            ^~~

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