Submission #634547

#	Time	Username	Problem	Language	Result	Execution time	Memory
634547		Theo830	Min-max tree (BOI18_minmaxtree)	C++17	36 / 100	1093 ms	49072 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vll>adj;
ll an[70005][20];
ll par[140005];
ll depth[70005];
vector<ll>exo[70005][2][2];
ll timi[70005][2];
set<ll>cur[140005];
ll find_par(ll a){
    if(par[a] == a){
        return a;
    }
    return par[a] = find_par(par[a]);
}
void enose(ll a,ll b){
    ll p1 = find_par(a);
    ll p2 = find_par(b);
    if(cur[p1].size() < cur[p2].size()){
        swap(p1,p2);
    }
    par[p1] = p2;
    for(auto x:cur[p1]){
        cur[p2].insert(x);
    }
    cur[p1].clear();
}
void build(ll idx,ll p){
    an[idx][0] = p;
    f(j,1,20){
        an[idx][j] = an[an[idx][j-1]][j-1];
    }
    for(auto x:adj[idx]){
        if(x != p){
            depth[x] = 1 + depth[idx];
            build(x,idx);
        }
    }
}
ll kth(ll a,ll k){
    ll pos = 0;
    while(k){
        if(k % 2){
            a = an[a][pos];
        }
        k /= 2;
        pos++;
    }
    return a;
}
void lca(ll a,ll b,bool m,ll c){
    if(depth[a] > depth[b]){
        swap(a,b);
    }
    ll A = a,B = b;
    b = kth(b,depth[b] - depth[a]);
    if(a == b){
        exo[a][m][1].pb(c);
        exo[B][m][0].pb(c);
        return;
    }
    for(ll j = 19;j >= 0;j--){
        if(an[a][j] != an[b][j]){
            a = an[a][j];
            b = an[b][j];
        }
    }
    exo[an[a][0]][m][1].pb(c);
    exo[B][m][0].pb(c);
    exo[A][m][0].pb(c);
}
void solve(ll idx,ll p){
    cur[idx*2].insert(0);
    cur[idx*2+1].insert(1e9+7);
    par[idx*2] = idx*2;
    par[idx*2+1] = idx*2+1;
    for(auto x:adj[idx]){
        if(x != p){
            solve(x,idx);
            enose(x*2,idx*2);
            enose(x*2+1,idx*2+1);
        }
    }
    f(j,0,2){
        for(auto x:exo[idx][j][0]){
            cur[find_par(idx*2+j)].insert(x);
        }
    }
    f(j,0,2){
        for(auto x:exo[idx][j][1]){
            cur[find_par(idx*2+j)].erase(x);
        }
    }
    timi[idx][0] = (*cur[find_par(idx*2)].rbegin());
    timi[idx][1] = (*cur[find_par(idx*2+1)].begin());
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    adj.assign(n+5,vll());
    f(i,0,n-1){
        ll a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    build(1,0);
    ll q;
    cin>>q;
    while(q--){
        char c;
        ll x,y,z;
        cin>>c>>x>>y>>z;
        lca(x,y,c == 'M',z);
    }
    solve(1,0);
    bool ek[n+5] = {0};
    ll posa[n+5];
    map<ll,ll>mp;
    map<ll,vll>adj;
    set<ii>ex;
    f(i,2,n+1){
        adj[timi[i][0]].pb(i);
        adj[timi[i][1]].pb(i);
        mp[timi[i][0]]++;
        mp[timi[i][1]]++;
    }
    for(auto x:mp){
        if(x.F != 0 && x.F != 1e9+7){
            ex.insert(ii(x.S,x.F));
        }
    }
    while(!ex.empty()){
        auto it = ex.begin();
        ii f = (*it);
        if(f.F == 0){
            assert(0);
            break;
        }
        ex.erase(f);
        while(ek[adj[f.S].back()]){
            adj[f.S].pop_back();
        }
        ek[adj[f.S].back()] = 1;
        posa[adj[f.S].back()] = f.S;
        ll c = 0;
        if(timi[adj[f.S].back()][0] == f.S){
            c ^= 1;
        }
        auto it2 = ex.lower_bound(ii(mp[timi[adj[f.S].back()][c]],timi[adj[f.S].back()][c]));
        if(it2 != ex.end() && (*it2) == ii(mp[timi[adj[f.S].back()][c]],timi[adj[f.S].back()][c])){
            f = (*it2);
            ex.erase(f);
            mp[timi[adj[f.S].back()][c]]--;
            f.F--;
            ex.insert(f);
        }
    }
    f(i,2,n+1){
        ll val;
        if(!ek[i]){
            val = timi[i][0];
        }
        else{
            val = posa[i];
        }
        cout<<i<<" "<<an[i][0]<<" "<<val<<"\n";
    }
}
/*
7
1 2
2 5
2 4
1 3
3 6
6 7
3
M 7 2 300
M 4 5 24
M 6 4 22
*/

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