oj.uz

Submission #810780

# Submission time Handle Problem Language Result Execution time Memory
810780 2023-08-06T15:12:52 Z Hakiers Torrent (COI16_torrent) C++17
0 / 100
 2000 ms 49948 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 7;
const int LOG = 18;
vector<pair<int, int>> G[MAXN];
int wsk[MAXN];
int depth[MAXN];
int dp[MAXN];
bool blocked[MAXN];
int jmp[MAXN][LOG + 1];
int root1, root2;
int res;
int n;

bool cmp(pair<int ,int> a, pair<int, int> b){

    return dp[a.first] > dp[b.first];
}

void dfs(int v, int p, int d = 0){

    depth[v] = d;
    jmp[v][0] = p;
    for(int k = 1; k <= LOG; k++)
        jmp[v][k] = jmp[jmp[v][k-1]][k-1];
    
    for(auto [u, id] : G[v]){
        if(u == p) continue;
        wsk[u] = id;
        dfs(u, v, d+1);
    }
}

void dfs_res(int v, int p){

    dp[v] = 0;
    for(auto [u, id] : G[v]){
        if(u == root1 || u == root2 || blocked[id] || u == p) continue;
        dfs_res(u, v);
    }

    sort(G[v].begin(), G[v].end(), cmp);
    int add = 1;

    for(auto [u, id] : G[v]){
        if(u == root1 || u == root2 || blocked[id] || u == p) continue;
        dp[v] = max(dp[v], dp[u] + add);
        add++;
    }

}

void solve(){

    int v = root1;
    int u = root2;
    /*
    for(int k = LOG; k >= 0; k--){
        blocked[wsk[jmp[u][k]]] = true;
        dfs_res(root1, root1);
        dfs_res(root2, root2);
        if(depth[v] < depth[jmp[u][k]] && max(dp[root1], dp[root2]) <= res){
            blocked[wsk[jmp[u][k]]] = false;
            res = max(dp[root1], dp[root2]);
            u = jmp[u][k];
        }
        blocked[wsk[jmp[u][k]]] = false;
    }
    */

    while(depth[v] < depth[u]){
        if(2*(depth[u] - depth[v]) <= depth[root2] - depth[root1])
        blocked[wsk[u]] = true;
        dfs_res(root1, root1);
        dfs_res(root2, root2);
        blocked[wsk[u]] = false;

        u = jmp[u][0];
    }
    

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> root1 >> root2;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
    }

    dfs(root1, root1);
    dfs_res(root1, root1);
    dfs_res(root2, root2);

    res = max(dp[root1], dp[root2]);
    /*
    for(int i = 1; i <= n; i++){
        blocked[wsk[i]] = true;

        dfs_res(root1, root1);
        dfs_res(root2, root2);

        res = min(res, max(dp[root1], dp[root2]));

        blocked[wsk[i]] = false;
    }
    */
    solve();

    cout << res << endl;


}

Subtask #1
0 / 31.0

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

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 49948 KB Time limit exceeded
2 Halted 0 ms 0 KB -