Submission #1227869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227869		Sir_Ahmed_Imran	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	58 ms	14524 KiB

minmaxtree

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 70001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int w[N];
int par[N];
int dept[N];
int p[N][17];
vector<int> a[N];

int root(int v){
    if(!par[v]) return v;
    par[v] = root(par[v]);
    return par[v];
}

void join(int v, int u){
    v = root(v), u = root(u);
    if(v == u) return;
    par[u] = v;
}

void dfs(int v, int u){
    p[v][0] = u;
    dept[v] = dept[u] + 1;
    for(auto & i : a[v])
        if(i != u) dfs(i, v);
}

int lca(int v, int u){
    if(dept[v] < dept[u])
        swap(v, u);
    for(int i = 16; i >= 0; i--)
        if(dept[p[v][i]] >= dept[u])
            v = p[v][i];
    if(v == u) return v;
    for(int i = 16; i >= 0; i--)
        if(p[v][i] != p[u][i])
            v = p[v][i], u = p[u][i];
    return p[v][0];
}

void solve(){
    char c;
    int n, q, v, u, x;
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> v >> u;
        a[v].append(u);
        a[u].append(v);
    }
    dfs(1, 0);
    for(int j = 0; j < 16; j++)
        for(int i = 1; i <= n; i++)
            p[i][j + 1] = p[p[i][j]][j];
    cin >> q;
    vector<pair<int, pii>> vec;
    for(int i = 0; i < q; i++){
        cin >> c >> v >> u >> x;
        vec.append({x, {v, u}});
    }
    sort(all(vec));
    for(auto & [i, j] : vec){
        v = j.ff, u = j.ss;
        x = lca(v, u);
        v = root(v);
        u = root(u);
        while(dept[v] > dept[x]){
            w[v] = i;
            join(p[v][0], v);
            v = root(v);
        }
        while(dept[u] > dept[x]){
            w[u] = i;
            join(p[u][0], u);
            u = root(u);
        }
    }
    for(int i = 2; i <= n; i++)
        cout << p[i][0] << ' ' << i << ' ' << w[i] << nl;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42