제출 #634518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634518		Theo830	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	233 ms	48280 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;
typedef long long 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[70005];
ll depth[70005];
set<ll>exo[70005][2][2];
ll timi[70005][2];
void build(ll idx,ll p){
    an[idx][0] = p;
    f(j,1,20){
        an[idx][j] = an[an[idx][j-1]][j-1];
    }
    par[idx] = p;
    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){
        assert(depth[B] != depth[a]);
        b = kth(B,depth[B] - depth[a] - 1);
        exo[b][m][0].insert(c);
        exo[B][m][1].insert(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[b][m][0].insert(c);
    exo[a][m][0].insert(c);
    exo[B][m][1].insert(c);
    exo[A][m][1].insert(c);
}
set<ll>cur[2];
void solve(ll idx,ll p){
    f(j,0,2){
        for(auto x:exo[idx][j][0]){
            cur[j].insert(x);
        }
    }
    timi[idx][0] = (*cur[0].rbegin());
    timi[idx][1] = (*cur[1].begin());
    f(j,0,2){
        for(auto x:exo[idx][j][1]){
            cur[j].erase(x);
        }
    }
    for(auto x:adj[idx]){
        if(x != p){
            solve(x,idx);
        }
    }
    f(j,0,2){
        for(auto x:exo[idx][j][1]){
            cur[j].insert(x);
        }
    }
    f(j,0,2){
        for(auto x:exo[idx][j][0]){
            cur[j].erase(x);
        }
    }
}
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);
    }
    cur[1].insert(1e9+7);
    cur[0].insert(0);
    /*
    f(i,1,n+1){
        cout<<i<<"\n";
        cout<<"vale maxi\n";
        for(auto x:exo[i][1][0]){
            cout<<x<<" ";
        }
        cout<<"\n";
        cout<<"vale mini\n";
        for(auto x:exo[i][0][0]){
            cout<<x<<" ";
        }
        cout<<"\n";
        cout<<"fkale maxi\n";
        for(auto x:exo[i][1][1]){
            cout<<x<<" ";
        }
        cout<<"\n";
        cout<<"fkale mini\n";
        for(auto x:exo[i][0][1]){
            cout<<x<<" ";
        }
        cout<<"\n";
        cout<<"\n";
    }
    */
    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){
        //cout<<timi[i][0]<<" "<<timi[i][1]<<"\n";
        adj[timi[i][0]].pb(i);
        adj[timi[i][1]].pb(i);
        mp[timi[i][0]]++;
        mp[timi[i][1]]++;
    }
    for(auto x:mp){
        ex.insert(ii(x.S,x.F));
    }
    while(!ex.empty()){
        auto it = ex.begin();
        ii f = (*it);
        if(f.F == 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<<" "<<par[i]<<" "<<val<<"\n";
    }
}

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