oj.uz

Submission #458841

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

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

const int N = 70000;
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});
        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;
        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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18380 KB Output is correct
2 Correct 13 ms 18380 KB Output is correct
3 Correct 11 ms 18380 KB Output is correct
4 Correct 12 ms 18380 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 54136 KB Output is correct
2 Correct 432 ms 47504 KB Output is correct
3 Correct 443 ms 50424 KB Output is correct
4 Correct 410 ms 55976 KB Output is correct
5 Correct 412 ms 49880 KB Output is correct
6 Correct 419 ms 49136 KB Output is correct
7 Correct 414 ms 47616 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 40704 KB Output is correct
2 Correct 227 ms 40884 KB Output is correct
3 Correct 206 ms 44784 KB Output is correct
4 Correct 204 ms 47736 KB Output is correct
5 Correct 256 ms 42820 KB Output is correct
6 Correct 277 ms 44236 KB Output is correct
7 Correct 279 ms 42052 KB Output is correct
8 Correct 229 ms 41820 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18380 KB Output is correct
2 Correct 13 ms 18380 KB Output is correct
3 Correct 11 ms 18380 KB Output is correct
4 Correct 12 ms 18380 KB Output is correct
5 Correct 431 ms 54136 KB Output is correct
6 Correct 432 ms 47504 KB Output is correct
7 Correct 443 ms 50424 KB Output is correct
8 Correct 410 ms 55976 KB Output is correct
9 Correct 412 ms 49880 KB Output is correct
10 Correct 419 ms 49136 KB Output is correct
11 Correct 414 ms 47616 KB Output is correct
12 Correct 216 ms 40704 KB Output is correct
13 Correct 227 ms 40884 KB Output is correct
14 Correct 206 ms 44784 KB Output is correct
15 Correct 204 ms 47736 KB Output is correct
16 Correct 256 ms 42820 KB Output is correct
17 Correct 277 ms 44236 KB Output is correct
18 Correct 279 ms 42052 KB Output is correct
19 Correct 229 ms 41820 KB Output is correct
20 Correct 458 ms 51548 KB Output is correct
21 Correct 389 ms 47208 KB Output is correct
22 Correct 424 ms 47280 KB Output is correct
23 Correct 421 ms 47940 KB Output is correct
24 Correct 619 ms 61936 KB Output is correct
25 Correct 601 ms 64584 KB Output is correct
26 Correct 574 ms 62856 KB Output is correct
27 Correct 633 ms 61108 KB Output is correct
28 Correct 519 ms 53724 KB Output is correct
29 Correct 585 ms 53964 KB Output is correct
30 Correct 544 ms 51392 KB Output is correct
31 Correct 453 ms 51428 KB Output is correct
32 Correct 521 ms 52952 KB Output is correct
33 Correct 481 ms 51136 KB Output is correct
34 Correct 450 ms 51188 KB Output is correct
35 Correct 464 ms 50868 KB Output is correct