oj.uz

답안 #1068200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068200 2024-08-21T08:28:48 Z _8_8_ Unique Cities (JOI19_ho_t5) C++17
0 / 100
 115 ms 39828 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],zap = 0;
void solve(int x,int y) {
    zap++;
    vector<bool> ok(n + 1,0),l(n+1,1);
    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;
            l[v] = false;
            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);
            }
        }
    }
    map<int,int> cc;
    set<pair<int,int>> d;
    for(int i = 1;i <= n;i++) {
        if(i != y && col[di[i]] == 1) {
            d.insert({dep[i],c[i]});
            cc[c[i]]++;
        }
    }
    int cur = 0;
    function<void(int,int)> paint = [&](int v,int pr){
        vector<int> a;
        for(int to:g[v]) {
            if(ok[to] || to == pr) continue;
            a.push_back(to);
        }
        if((int)a.size() == 1) {

        }
    };
    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()).first);
            if(val <= cur) {
                auto [_d,co] = (*d.rbegin());
                cc[co]--;
                if(cc[co] == 0) {
                    cc.erase(co);
                }
                d.erase(*d.rbegin());
            } else break;
        }
        if((int)cc.size()){
            dp[v] = (int)cc.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 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);
    memset(dp,-1,sizeof(dp));
    solve(d1,d2);
    solve(d2,d1);
    // go(d1);
    for(int i = 1; i <= n; i++) {
        cout << i << ' ' << 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 27736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 35080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 39828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 27736 KB Output isn't correct
2 Halted 0 ms 0 KB -