oj.uz

Submission #810669

# Submission time Handle Problem Language Result Execution time Memory
810669 2023-08-06T13:58:26 Z Hakiers Torrent (COI16_torrent) C++17
0 / 100
 831 ms 51672 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 7;
const int LOG = 17;
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[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[jmp[u][k]] = false;
            res = max(dp[root1], dp[root2]);
            u = jmp[u][k];
        }
        blocked[jmp[u][k]] = false;
    }

}

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]);
    solve();

    cout << res << endl;


}

Compilation message

torrent.cpp: In function 'void dfs_res(int, int)':
torrent.cpp:40:14: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   40 |         if(u == root1 | u == root2 || blocked[id] || u == p) continue;
      |            ~~^~~~~~~~
torrent.cpp:48:14: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   48 |         if(u == root1 | u == root2 || blocked[id] || u == p) continue;
      |            ~~^~~~~~~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 Correct 831 ms 49960 KB Output is correct
2 Incorrect 827 ms 51672 KB Output isn't correct
3 Halted 0 ms 0 KB -