oj.uz

답안 #634544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634544 2022-08-24T14:39:23 Z Theo830 Min-max tree (BOI18_minmaxtree) C++17
36 / 100
 1000 ms 47612 KB 
#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[70005];
ll depth[70005];
vector<ll>exo[70005][2][2];
ll timi[70005][2];
set<ll>cur[70005][2];
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[0][p1].size() + cur[1][p1].size() < cur[0][p2].size() + cur[1][p2].size()){
        swap(p1,p2);
    }
    par[p1] = p2;
    for(auto x:cur[p1][0]){
        cur[p2][0].insert(x);
    }
    for(auto x:cur[p1][1]){
        cur[p2][1].insert(x);
    }
    cur[p1][0].clear();
    cur[p1][1].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][0].insert(0);
    cur[idx][1].insert(1e9+7);
    par[idx] = idx;
    for(auto x:adj[idx]){
        if(x != p){
            solve(x,idx);
            enose(x,idx);
        }
    }
    ll v = idx;
    idx = find_par(idx);
    f(j,0,2){
        for(auto x:exo[v][j][0]){
            cur[idx][j].insert(x);
        }
    }
    f(j,0,2){
        for(auto x:exo[v][j][1]){
            cur[idx][j].erase(x);
        }
    }
    timi[v][0] = (*cur[idx][0].rbegin());
    timi[v][1] = (*cur[idx][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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13396 KB Output is correct
2 Correct 7 ms 13408 KB Output is correct
3 Correct 9 ms 13396 KB Output is correct
4 Correct 7 ms 13396 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 47612 KB Output is correct
2 Correct 290 ms 42180 KB Output is correct
3 Execution timed out 1092 ms 32420 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 32348 KB Output is correct
2 Correct 157 ms 32516 KB Output is correct
3 Correct 162 ms 35576 KB Output is correct
4 Correct 171 ms 39520 KB Output is correct
5 Correct 187 ms 33612 KB Output is correct
6 Correct 205 ms 34560 KB Output is correct
7 Correct 181 ms 33460 KB Output is correct
8 Correct 191 ms 33076 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13396 KB Output is correct
2 Correct 7 ms 13408 KB Output is correct
3 Correct 9 ms 13396 KB Output is correct
4 Correct 7 ms 13396 KB Output is correct
5 Correct 374 ms 47612 KB Output is correct
6 Correct 290 ms 42180 KB Output is correct
7 Execution timed out 1092 ms 32420 KB Time limit exceeded
8 Halted 0 ms 0 KB -