oj.uz

Submission #209320

# Submission time Handle Problem Language Result Execution time Memory
209320 2020-03-13T17:17:29 Z Nashik Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 273 ms 35960 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
//ifstream cin("minmaxtree.in");
//ofstream cout("minmaxtree.out");
int t[70005],euclid[200005],niv[200005],cnt,put[20],lg[300005],rmq[20][200005],fr[200005],tata[200005],tatac[200005],ap[200005],maxim[200005],minim[200005],cod[200005],viz[70005],st[70005],dr[70005];
vector<int> temp[70005],v[70005];
vector<int> graf[70005];
struct query{
    int a,b,c;
}mi[70005],ma[70005];
void dfs(int nod,int h){
    t[nod]=1;
    euclid[++cnt]=nod;
    niv[cnt]=h;
    for(auto u:temp[nod]){
        if(t[u]==1)
            continue;
        v[nod].push_back(u);
        tata[u]=nod;
        tatac[u]=nod;
        dfs(u,h+1);
        euclid[++cnt]=nod;
        niv[cnt]=h;
    }
}
void add(int a,int b){
    graf[a].push_back(b);
}
int maa(int a,int b){
    if(niv[a]>niv[b]){
        return b;
    }
    return a;
}
int lca(int st,int dr){
    int dist=dr-st+1;
    int e=lg[dist];
    return euclid[maa(rmq[e][st],rmq[e][dr-put[e]+1])];
}
int find_lca(int a,int b){
    a=fr[a];
    b=fr[b];
    if(a>b)
        swap(a,b);
    return lca(a,b);
}
bool misort(query a,query b){
    return a.c<b.c;
}
bool masort(query a,query b){
    return a.c>b.c;
}
int mai_jos(int a,int b){
    if(niv[fr[a]]>niv[fr[b]])
        return true;
    return false;
}
void update(int jos,int sus,int val,bool ok,int ind){
    int cur=jos;
    while(mai_jos(cur,sus)==true){
        cur=tata[cur];
    }
    int nex=cur;
    cur=jos;
    while(mai_jos(cur,sus)==true){
        if(cur==0 or cur==1)
            break;
        int aux=tata[cur];
        tata[cur]=nex;
        if(ap[cod[cur]]==0){
            if(ok==0)
                maxim[cod[cur]]=ind;
            else
                minim[cod[cur]]=ind;
            ap[cod[cur]]=1;
        }
        cur=aux;
    }
}
bool cup(int w){
    if(viz[w]==1)
        return 0;
    viz[w]=1;
    for(auto u:graf[w]){
        if(dr[u]==0){
            st[w]=u;
            dr[u]=w;
            return 1;
        }
    }
    for(auto u:graf[w]){
        if(cup(dr[u])==1){
            st[w]=u;
            dr[u]=w;
            return 1;
        }
    }
    return 0;
}
pair<int,int> muchie[70005];
int main()
{
    int n,a,b,k,c,c1=0,c2=0;
    char ch;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        temp[a].push_back(b);
        temp[b].push_back(a);
    }
    dfs(1,1);
    for(int i=cnt;i>=1;i--){
        fr[euclid[i]]=i;
    }
    for(int i=1;i<=cnt;i++){
        rmq[0][i]=i;
    }
    put[0]=1;
    for(int i=1;i<=18;i++){
        put[i]=put[i-1]*2;
        lg[put[i]]++;
    }
    for(int i=1;i<=200000;i++){
        lg[i]+=lg[i-1];
    }
    for(int i=1;i<=18;i++){
        for(int j=1;j<=cnt;j++){
            if(j+put[i]-1>cnt)
                break;
            rmq[i][j]=maa(rmq[i-1][j],rmq[i-1][j+put[i-1]]);
        }
    }
    cin>>k;
    cin.get();
    for(int i=1;i<=k;i++){
        cin>>ch>>a>>b>>c;
        cin.get();
        if(ch=='m'){
            mi[++c1].a=a;
            mi[c1].b=b;
            mi[c1].c=c;
        }
        else{
            ma[++c2].a=a;
            ma[c2].b=b;
            ma[c2].c=c;
        }
    }
    sort(mi+1,mi+c1+1,masort);
    sort(ma+1,ma+c2+1,misort);
    for(int i=1;i<n;i++){
        maxim[i]=-1;
        minim[i]=-1;
    }
    //for(int i=1;i<=n;i++)
        //cout<<tata[i]<<" ";
    //cout<<"\n";
    int contor=0;
    for(int i=2;i<=n;i++){
        cod[i]=++contor;
        muchie[contor]=make_pair(i,tata[i]);
    }

    for(int i=1;i<=c1;i++){
        //cout<<i<<"\n";
        int lca=find_lca(mi[i].a,mi[i].b);
        //cout<<lca<<" ";
        update(mi[i].a,lca,mi[i].c,1,i);
        update(mi[i].b,lca,mi[i].c,1,i);
    }
    for(int i=1;i<=n;i++){
        ap[i]=0;
        tata[i]=tatac[i];
    }
    for(int i=1;i<=c2;i++){
        int lca=find_lca(ma[i].a,ma[i].b);
        update(ma[i].a,lca,ma[i].c,0,i+c1);
        update(ma[i].b,lca,ma[i].c,0,i+c1);
    }
    for(int i=1;i<n;i++){
        //cout<<i<<" "<<maxim[i]<<" "<<minim[i]<<"\n";
        if(maxim[i]!=-1)
            graf[i].push_back(maxim[i]);
        if(minim[i]!=-1)
            graf[i].push_back(minim[i]);
    }
    int co=0,pco;
    do{
        pco=co;
        for(int i=1;i<n;i++){
            viz[i]=0;
        }
        for(int i=1;i<n;i++){
            if(st[i]==0){
                co+=cup(i);
            }
        }
    }while(co!=pco);
    //cout<<"\n\n";
    for(int i=1;i<n;i++){
        cout<<muchie[i].first<<" "<<muchie[i].second<<" ";
        //cout
        if(st[i]!=0){
            //cout<<i<<" ";
            if(st[i]<=c1){
                cout<<mi[st[i]].c<<"\n";
            }
            else{
                cout<<ma[st[i]-c1].c<<"\n";
            }
        }
        else{
            if(maxim[i]!=-1){
                cout<<ma[maxim[i]-c1].c<<"\n";
                continue;
            }
            if(minim[i]!=-1){
                cout<<mi[minim[i]].c<<"\n";
                continue;
            }
            cout<<1<<"\n";
        }
    }

    return 0;
}

/*
4
1 2
2 3
3 4
2
m 1 3 20
m 1 4 15
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 8 ms 6140 KB Output is correct
3 Correct 9 ms 6136 KB Output is correct
4 Correct 8 ms 6136 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 31224 KB Output is correct
2 Correct 247 ms 29048 KB Output is correct
3 Correct 252 ms 31864 KB Output is correct
4 Correct 259 ms 34936 KB Output is correct
5 Correct 241 ms 31352 KB Output is correct
6 Correct 262 ms 30840 KB Output is correct
7 Correct 258 ms 29816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 25336 KB Output is correct
2 Correct 169 ms 26976 KB Output is correct
3 Correct 169 ms 30968 KB Output is correct
4 Correct 174 ms 32376 KB Output is correct
5 Correct 183 ms 28408 KB Output is correct
6 Correct 192 ms 29176 KB Output is correct
7 Correct 190 ms 28152 KB Output is correct
8 Correct 187 ms 27944 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 8 ms 6140 KB Output is correct
3 Correct 9 ms 6136 KB Output is correct
4 Correct 8 ms 6136 KB Output is correct
5 Correct 263 ms 31224 KB Output is correct
6 Correct 247 ms 29048 KB Output is correct
7 Correct 252 ms 31864 KB Output is correct
8 Correct 259 ms 34936 KB Output is correct
9 Correct 241 ms 31352 KB Output is correct
10 Correct 262 ms 30840 KB Output is correct
11 Correct 258 ms 29816 KB Output is correct
12 Correct 169 ms 25336 KB Output is correct
13 Correct 169 ms 26976 KB Output is correct
14 Correct 169 ms 30968 KB Output is correct
15 Correct 174 ms 32376 KB Output is correct
16 Correct 183 ms 28408 KB Output is correct
17 Correct 192 ms 29176 KB Output is correct
18 Correct 190 ms 28152 KB Output is correct
19 Correct 187 ms 27944 KB Output is correct
20 Correct 264 ms 29176 KB Output is correct
21 Correct 223 ms 28280 KB Output is correct
22 Correct 226 ms 28408 KB Output is correct
23 Correct 235 ms 28920 KB Output is correct
24 Correct 273 ms 34168 KB Output is correct
25 Correct 266 ms 35960 KB Output is correct
26 Correct 265 ms 35576 KB Output is correct
27 Correct 261 ms 33656 KB Output is correct
28 Correct 269 ms 30744 KB Output is correct
29 Correct 262 ms 30712 KB Output is correct
30 Correct 241 ms 29816 KB Output is correct
31 Correct 257 ms 29944 KB Output is correct
32 Correct 263 ms 30072 KB Output is correct
33 Correct 250 ms 29816 KB Output is correct
34 Correct 253 ms 29688 KB Output is correct
35 Correct 248 ms 29560 KB Output is correct