oj.uz

Submission #963682

# Submission time Handle Problem Language Result Execution time Memory
963682 2024-04-15T13:12:03 Z Whisper Torrent (COI16_torrent) C++17
100 / 100
 511 ms 47632 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
const int MAX = 3e5 + 5;
int numNode, nodeU, nodeV;
struct Edge{
    int u, v;
    Edge(){}
    Edge(int _u, int _v, int _id): u(_u), v(_v){}

    int other(int x){return (x ^ u ^ v); }
} edge[MAX];

vector<int> G[MAX];
int par[MAX];
int tin[MAX], tout[MAX], cnt = 0;

int color[MAX];

vector<int> node;
int to_edge[MAX];

void dfs(int u, int p = -1){
    tin[u] = ++cnt;
    par[u] = p;
    for (int&i : G[u]){
        int v = edge[i].other(u);
        if(v ^ p){
            to_edge[v] = i;
            dfs(v, u);
        }
    }
    tout[u] = cnt;
}
bool inside(int root, int node){
    return tin[root] <= tin[node] && tout[node] <= tout[root];
}
int dp[MAX];
int dfs_dp(int u, int col, int p = -1){
    dp[u] = 0;
    vector<int> store;
    for (int&i : G[u]){
        int v = edge[i].other(u);
        if((v ^ p) && color[i] == col){
            store.push_back(dfs_dp(v, col, u));
        }
    }
    sort(store.rbegin(), store.rend());
    for (int i = 0; i < (int)store.size(); ++i){
        maximize(dp[u], store[i] + i + 1);
    }
    return dp[u];
}
int Ask(int pos, bool Search){
    int root = node[pos];
    for (int i = 1; i <= numNode; ++i){
        if (i != root && inside(root, i)){
            color[to_edge[i]] = 2;
        }
        else{
            color[to_edge[i]] = 1;
        }
    }
    color[to_edge[root]] = 3;
    int a = dfs_dp(nodeU, 1), b = dfs_dp(nodeV, 2);
    if(Search) return (a >= b);
    return max(a, b);
}
void Whisper(){
    cin >> numNode >> nodeU >> nodeV;
    for (int i = 1; i < numNode; ++i){
        cin >> edge[i].u >> edge[i].v;
        G[edge[i].u].emplace_back(i);
        G[edge[i].v].emplace_back(i);
    }

    dfs(nodeU);
    int vertex = nodeV;
    while (vertex != nodeU){
        node.push_back(vertex);
        vertex = par[vertex];
    }
    int res = LINF, ID = -1;
    int l = 0, r = node.size() - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(Ask(mid, 1)) ID = mid, l = mid + 1;
        else r = mid - 1;
    }
    if (ID != -1) minimize(res, Ask(ID, 0));
    if (ID != (int)node.size() - 1) minimize(res, Ask(ID + 1, 0));
    cout << res << '\n';
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18776 KB Output is correct
2 Correct 5 ms 18776 KB Output is correct
3 Correct 5 ms 18780 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 43860 KB Output is correct
2 Correct 490 ms 45384 KB Output is correct
3 Correct 471 ms 47096 KB Output is correct
4 Correct 415 ms 46292 KB Output is correct
5 Correct 399 ms 43348 KB Output is correct
6 Correct 380 ms 44108 KB Output is correct
7 Correct 360 ms 47632 KB Output is correct