oj.uz

Submission #458831

# Submission time Handle Problem Language Result Execution time Memory
458831 2021-08-08T06:24:51 Z JovanB Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 605 ms 100548 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;
const int LOG = 16;

int in[N+5], out[N+5], sz[N+5];
vector <int> graf[N+5];
int par[N+5][LOG+1];

int tjm;

void dfs_lca(int v, int p){
    in[v] = ++tjm;
    sz[v] = 1;
    par[v][0] = p;
    for(int j=1; j<=LOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]){
        if(c == p) continue;
        dfs_lca(c, v);
        sz[v] += sz[c];
    }
    out[v] = ++tjm;
}

bool is_parent(int a, int b){
    return a == 0 || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=LOG; j>=0; j--) if(!is_parent(par[a][j], b)) a = par[a][j];
    return par[a][0];
}

int qa[N+5], qb[N+5], qc[N+5];
char typ[N+5];

vector <int> vec[2][N+5];
set <int> vals[2][N+5];

int gde[N+5];
int mxl[N+5], mnr[N+5];

const int INF = 1000000007;

void dodaj(int v){
    sort(vec[0][v].begin(), vec[0][v].end());
    reverse(vec[0][v].begin(), vec[0][v].end());
    for(auto x : vec[0][v]){
        if(x > 0) vals[0][gde[v]].insert(x);
        else vals[0][gde[v]].erase(-x);
    }
    sort(vec[1][v].begin(), vec[1][v].end());
    reverse(vec[1][v].begin(), vec[1][v].end());
    for(auto x : vec[1][v]){
        if(x > 0) vals[1][gde[v]].insert(x);
        else vals[1][gde[v]].erase(-x);
    }
}

void dfs_calc(int v, int p){
    mnr[v] = INF;
    int mx = 0;
    for(auto c : graf[v]){
        if(c == p) continue;
        dfs_calc(c, v);
        if(sz[c] >= sz[mx]) mx = c;
    }
    if(!mx){
        gde[v] = v;
        dodaj(v);
        if(vals[0][gde[v]].size()) mxl[v] = *vals[0][gde[v]].rbegin();
        if(vals[1][gde[v]].size()) mnr[v] = *vals[1][gde[v]].begin();
        return;
    }
    gde[v] = gde[mx];
    for(auto c : graf[v]){
        if(c == p || c == mx) continue;
        for(auto x : vals[0][gde[c]]) vals[0][gde[v]].insert(x);
        for(auto x : vals[1][gde[c]]) vals[1][gde[v]].insert(x);
        vals[0][gde[c]].clear();
        vals[1][gde[c]].clear();
    }
    dodaj(v);
    if(vals[0][gde[v]].size()) mxl[v] = *vals[0][gde[v]].rbegin();
    if(vals[1][gde[v]].size()) mnr[v] = *vals[1][gde[v]].begin();
}

map <int, int> kome;
set <int> bgraf[2*N+5];
int val[N+5];

set <pair <int, int>> q;

void clr(int v){
    for(auto c : bgraf[v]){
        q.erase({bgraf[c].size(), c});
        assert(bgraf[c].find(v) != bgraf[c].end());
        bgraf[c].erase(v);
        if(bgraf[c].size()) q.insert({bgraf[c].size(), c});
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs_lca(1, 0);
    int qrs;
    cin >> qrs;
    for(int t=1; t<=qrs; t++){
        cin >> typ[t] >> qa[t] >> qb[t] >> qc[t];
        qc[t]++;
        kome[qc[t]] = t;
        if(typ[t] == 'm'){
            vec[0][qa[t]].push_back(qc[t]);
            vec[0][qb[t]].push_back(qc[t]);
            vec[0][lca(qa[t], qb[t])].push_back(-qc[t]);
        }
        else{
            vec[1][qa[t]].push_back(qc[t]);
            vec[1][qb[t]].push_back(qc[t]);
            vec[1][lca(qa[t], qb[t])].push_back(-qc[t]);
        }
    }
    dfs_calc(1, 0);
    for(int i=2; i<=n; i++){
        if(mxl[i]){
            int v = kome[mxl[i]];
            bgraf[v].insert(N + i);
            bgraf[N + i].insert(v);
        }
        if(mnr[i] != INF){
            int v = kome[mnr[i]];
            bgraf[v].insert(N + i);
            bgraf[N + i].insert(v);
        }
    }
    for(int i=1; i<=qrs; i++) q.insert({bgraf[i].size(), i});
    for(int i=2; i<=n; i++) q.insert({bgraf[N + i].size(), N + i});
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        if(bgraf[v].empty()) continue;
        if(bgraf[v].size() > 2){
            for(auto c : bgraf[v]){
                //assert(bgraf[c].size() >= bgraf[v].size());
                assert(q.find({bgraf[c].size(), c}) != q.end());
            }
        }
        int c = *bgraf[v].begin();
        if(v > N) swap(v, c);
        val[c - N] = qc[v];
        q.erase({bgraf[v].size(), v});
        q.erase({bgraf[c].size(), c});
        bgraf[v].erase(c);
        bgraf[c].erase(v);
        clr(v);
        clr(c);
        bgraf[v].clear();
        bgraf[c].clear();
    }
    for(int i=2; i<=n; i++){
        cout << par[i][0] << " " << i << " ";
        if(val[i]) cout << val[i] - 1 << "\n";
        else if(mxl[i]) cout << mxl[i] - 1 << "\n";
        else if(mnr[i] != INF) cout << mnr[i] - 1 << "\n";
        else cout << "1\n";
    }
    return 0;
}

/*
6
1 2
2 4
1 6
1 3
6 5
2
m 4 1 2
M 4 6 3
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 52044 KB Output is correct
2 Correct 28 ms 51928 KB Output is correct
3 Correct 28 ms 52012 KB Output is correct
4 Correct 28 ms 52036 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 87856 KB Output is correct
2 Correct 367 ms 81200 KB Output is correct
3 Correct 379 ms 84208 KB Output is correct
4 Correct 405 ms 89708 KB Output is correct
5 Correct 389 ms 83640 KB Output is correct
6 Correct 375 ms 82884 KB Output is correct
7 Correct 348 ms 81464 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 74244 KB Output is correct
2 Correct 235 ms 75764 KB Output is correct
3 Correct 230 ms 79600 KB Output is correct
4 Correct 224 ms 82628 KB Output is correct
5 Correct 249 ms 77764 KB Output is correct
6 Correct 291 ms 79172 KB Output is correct
7 Correct 268 ms 77104 KB Output is correct
8 Correct 323 ms 76728 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 52044 KB Output is correct
2 Correct 28 ms 51928 KB Output is correct
3 Correct 28 ms 52012 KB Output is correct
4 Correct 28 ms 52036 KB Output is correct
5 Correct 395 ms 87856 KB Output is correct
6 Correct 367 ms 81200 KB Output is correct
7 Correct 379 ms 84208 KB Output is correct
8 Correct 405 ms 89708 KB Output is correct
9 Correct 389 ms 83640 KB Output is correct
10 Correct 375 ms 82884 KB Output is correct
11 Correct 348 ms 81464 KB Output is correct
12 Correct 226 ms 74244 KB Output is correct
13 Correct 235 ms 75764 KB Output is correct
14 Correct 230 ms 79600 KB Output is correct
15 Correct 224 ms 82628 KB Output is correct
16 Correct 249 ms 77764 KB Output is correct
17 Correct 291 ms 79172 KB Output is correct
18 Correct 268 ms 77104 KB Output is correct
19 Correct 323 ms 76728 KB Output is correct
20 Correct 485 ms 87480 KB Output is correct
21 Correct 421 ms 82780 KB Output is correct
22 Correct 423 ms 82996 KB Output is correct
23 Correct 404 ms 83652 KB Output is correct
24 Correct 605 ms 98056 KB Output is correct
25 Correct 595 ms 100548 KB Output is correct
26 Correct 512 ms 98696 KB Output is correct
27 Correct 584 ms 96928 KB Output is correct
28 Correct 512 ms 89744 KB Output is correct
29 Correct 487 ms 89964 KB Output is correct
30 Correct 508 ms 87124 KB Output is correct
31 Correct 456 ms 87204 KB Output is correct
32 Correct 551 ms 89112 KB Output is correct
33 Correct 469 ms 87096 KB Output is correct
34 Correct 456 ms 87104 KB Output is correct
35 Correct 488 ms 86460 KB Output is correct