Submission #299138

#	Time	Username	Problem	Language	Result	Execution time	Memory
299138		Hehehe	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	367 ms	177860 KiB

minmaxtree

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e6 + 11;
const int X = 1e6;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int depth[N], F[N], l[N], r[N], n, m, k;
int E[N*4], lg[N*4], first[N], viz[N], P[N], dp_min[N], dp_max[N];
vector<int> v[N], g[N];
map<int, int> poz;
pi rmq[30][N];

struct yes{
    int tip, x, y, val;
};

yes q[N], w[N];

void dfs(int nod, int p){
    E[++k] = nod;
    first[nod] = k;
    depth[nod] = depth[p] + 1;
    F[nod] = P[nod] = p;
    for(auto it : v[nod]){
        if(it == p)continue;
        dfs(it, nod);
        E[++k] = nod;
    }
}

int get_lca(int x, int y){
    int X = first[x], Y = first[y];
    if(X > Y)swap(X, Y);

    int lvl = lg[Y - X + 1];
    pi ans = min(rmq[lvl][X], rmq[lvl][Y - (1 << lvl) + 1]);
    return E[ans.ss];
}

int cpl(int nod){
    if(viz[nod])return 0;

    viz[nod] = 1;
    for(auto it : g[nod]){
        if(r[it] == 0 || cpl(r[it])){
            l[nod] = it;
            r[it] = nod;
            return 1;
        }
    }

    return 0;
}

void solve(){

    cin >> n;

    for(int i = 1, x, y; i < n; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    for(int i = 1; i <= k; i++){
        rmq[0][i] = mp(depth[E[i]], i);
    }

    for(int i = 1; (1 << i) <= k; i++){
        for(int j = 1; j <= k; j++){
            rmq[i][j] = rmq[i - 1][j];
            if (j + (1 << (i - 1)) <= k && rmq[i - 1][j + (1 << (i - 1))].ff < rmq[i][j].ff)
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
        }
    }

    for(int i = 2; i <= k; i++){
        lg[i] = lg[i / 2] + 1;
    }

    cin >> m;
    int el = 0;
    for(int i = 1, x, y, val; i <= m; i++){
        char c;

        cin >> c >> x >> y >> val;

        int type = (c == 'M' ? 1 : 0);

        q[i] = {type, x, y, val};

        poz[val] = i;

        if(type)w[++el] = q[i];
    }

    sort(w + 1, w + el + 1, [](yes L, yes R){
         return L.val < R.val;
    });
    for(int i = 1; i <= el; i++){
        int x = w[i].x, y = w[i].y, val = w[i].val;

        int LCA = get_lca(x, y);

        for(int I : {x, y}){
            int nod = I;
            while (nod && depth[nod] > depth[LCA]){

                if(!dp_min[nod])dp_min[nod] = val;

                int aux = nod;
                nod = F[nod];
                F[aux] = LCA;
            }
        }
    }

    for(int i = 1; i <= n; i++)F[i] = P[i];

    el = 0;
    for(int i = 1; i <= n; i++){
        if(q[i].tip == 0)w[++el] = q[i];
    }

    sort(w + 1, w + el + 1, [](yes L, yes R){
         return L.val < R.val;
    });
    for(int i = el; i >= 1; i--){
        int x = w[i].x, y = w[i].y, val = w[i].val;

        int LCA = get_lca(x, y);

        for(int I : {x, y}){
            int nod = I;
            while (nod && depth[nod] > depth[LCA]){

                if(!dp_max[nod])dp_max[nod] = val;

                int aux = nod;
                nod = F[nod];
                F[aux] = LCA;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(dp_max[i]){
            int idx = poz[dp_max[i]];

            g[i].push_back(n + idx);
            g[n + idx].push_back (i);
        }

        if(dp_min[i]){
            int idx = poz[dp_min[i]];

            g[i].push_back(n + idx);
            g[n + idx].push_back(i);
        }
    }

    int ok = 1;

    while(ok){
        memset(viz, 0, sizeof(viz));
        ok = 0;
        for(int i = 1; i <= n; i++){
            if(!l[i] && cpl(i))ok = 1;
        }
    }

    for(int i = 2; i <= n; i++){
        cout << i << ' ' << P[i] << ' ';
        int idx = l[i];
        cout << (idx ? q[idx - n].val : max(dp_min[i],dp_max[i])) << '\n';
    }
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

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