oj.uz

Submission #1068051

# Submission time Handle Problem Language Result Execution time Memory
1068051 2024-08-21T06:57:32 Z _8_8_ Unique Cities (JOI19_ho_t5) C++17
0 / 100
 112 ms 35508 KB 
#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();
    }
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Incorrect 12 ms 23900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 31316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 35508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Incorrect 12 ms 23900 KB Output isn't correct
3 Halted 0 ms 0 KB -