oj.uz

Submission #601146

# Submission time Handle Problem Language Result Execution time Memory
601146 2022-07-21T11:58:41 Z alexander707070 Inside information (BOI21_servers) C++14
50 / 100
 564 ms 37700 KB 
#include<bits/stdc++.h>
#define MAXN 400007
using namespace std;

struct node{
    bool ok;
    int l,r;
};

int n,q,a[MAXN],b[MAXN],num;
char type[MAXN];
vector<int> v[MAXN];
int sz[MAXN],heavy[MAXN],head[MAXN];
int pos[MAXN],dep[MAXN],parent[MAXN];

void dfs(int x,int p,int dd){
    sz[x]=1; dep[x]=dd; parent[x]=p;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x,dd+1);
        if(sz[v[x][i]]>sz[heavy[x]]){
            heavy[x]=v[x][i];
        }
        sz[x]+=sz[v[x][i]];
    }
}

void decompose(int x,int p,int h){
    if(x==0)return;
    num++; pos[x]=num; head[x]=h;

    decompose(heavy[x],x,h);
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p or v[x][i]==heavy[x])continue;
        decompose(v[x][i],x,v[x][i]);
    }
}

node tree[2][4*MAXN];

node combine(int dir,node fr,node sc){
    if(fr.l==-1)return sc;
    if(sc.l==-1)return fr;
    if(dir==0){
        if(fr.ok and sc.ok and fr.r<sc.l){
            return {true,fr.l,sc.r};
        }else{
            return {false,fr.l,sc.r};
        }
    }else{
        if(fr.ok and sc.ok and fr.r>sc.l){
            return {true,fr.l,sc.r};
        }else{
            return {false,fr.l,sc.r};
        }
    }
}

void update(int dir,int v,int l,int r,int pos,int val){
    if(l==r){
        tree[dir][v]={true,val,val};
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(dir,2*v,l,tt,pos,val);
        else update(dir,2*v+1,tt+1,r,pos,val);
        tree[dir][v]=combine(dir,tree[dir][2*v],tree[dir][2*v+1]);
    }
}

node getval(int dir,int v,int l,int r,int ll,int rr){
    if(ll>rr){
        if(dir==0)return {true,-1,-1};
        else return {true,-1,-1};
    }
    if(l==ll and r==rr){
        return tree[dir][v];
    }else{
        int tt=(l+r)/2;
        return combine( dir, getval(dir,2*v,l,tt,ll,min(tt,rr)) , getval(dir,2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

bool query(int a,int b){
    node lt={true,-1,-1},rt={true,-1,-1};
    while(head[a]!=head[b]){
        if(dep[head[a]]>dep[head[b]]){
            lt=combine(1,getval(1,1,1,n,pos[head[a]],pos[a]),lt);
            a=parent[head[a]];
        }else{
            rt=combine(0,getval(0,1,1,n,pos[head[b]],pos[b]),rt);
            b=parent[head[b]];
        }
    }
    if(dep[a]<dep[b]){
        rt=combine(0,getval(0,1,1,n,pos[a]+1,pos[b]),rt);
    }else{
        lt=combine(1,getval(1,1,1,n,pos[b]+1,pos[a]),lt);
    }
    swap(lt.l,lt.r);
    return combine(0,lt,rt).ok;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n+q-1;i++){
        cin>>type[i];
        if(type[i]=='S'){
            cin>>a[i]>>b[i];
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        }else if(type[i]=='Q'){
            cin>>a[i]>>b[i];
        }else{
            cin>>a[i];
        }
    }

    dfs(1,0,1);
    decompose(1,0,1);

    num=0;
    for(int i=1;i<=n+q-1;i++){
        if(type[i]=='S'){
            num++;
            if(dep[a[i]]>dep[b[i]])swap(a[i],b[i]);
            update(0,1,1,n,pos[b[i]],num);
            update(1,1,1,n,pos[b[i]],num);  
        }else if(type[i]=='Q'){
            if(query(b[i],a[i])){
                cout<<"yes\n";
            }else{
                cout<<"no\n";
            }
        }else{
            cout<<0<<"\n";
        }
    }

    return 0;
}

Compilation message

servers.cpp: In function 'void dfs(int, int, int)':
servers.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
servers.cpp: In function 'void decompose(int, int, int)':
servers.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11108 KB Output is correct
2 Correct 187 ms 12968 KB Output is correct
3 Correct 93 ms 13004 KB Output is correct
4 Correct 116 ms 13168 KB Output is correct
5 Correct 76 ms 13276 KB Output is correct
6 Correct 94 ms 12984 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11108 KB Output is correct
2 Correct 187 ms 12968 KB Output is correct
3 Correct 93 ms 13004 KB Output is correct
4 Correct 116 ms 13168 KB Output is correct
5 Correct 76 ms 13276 KB Output is correct
6 Correct 94 ms 12984 KB Output is correct
7 Incorrect 59 ms 11980 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11240 KB Output is correct
2 Correct 186 ms 24936 KB Output is correct
3 Correct 226 ms 24980 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11240 KB Output is correct
2 Correct 186 ms 24936 KB Output is correct
3 Correct 226 ms 24980 KB Output is correct
4 Incorrect 45 ms 11164 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11084 KB Output is correct
2 Correct 222 ms 34440 KB Output is correct
3 Correct 213 ms 34380 KB Output is correct
4 Correct 179 ms 34340 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11084 KB Output is correct
2 Correct 222 ms 34440 KB Output is correct
3 Correct 213 ms 34380 KB Output is correct
4 Correct 179 ms 34340 KB Output is correct
5 Incorrect 41 ms 11188 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11144 KB Output is correct
2 Correct 549 ms 28052 KB Output is correct
3 Correct 254 ms 28032 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11144 KB Output is correct
2 Correct 549 ms 28052 KB Output is correct
3 Correct 254 ms 28032 KB Output is correct
4 Incorrect 67 ms 11964 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11124 KB Output is correct
2 Correct 191 ms 34328 KB Output is correct
3 Correct 210 ms 34380 KB Output is correct
4 Correct 181 ms 34420 KB Output is correct
5 Correct 72 ms 11184 KB Output is correct
6 Correct 542 ms 28080 KB Output is correct
7 Correct 226 ms 28100 KB Output is correct
8 Correct 528 ms 28560 KB Output is correct
9 Correct 253 ms 28512 KB Output is correct
10 Correct 192 ms 31896 KB Output is correct
11 Correct 271 ms 31108 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11124 KB Output is correct
2 Correct 191 ms 34328 KB Output is correct
3 Correct 210 ms 34380 KB Output is correct
4 Correct 181 ms 34420 KB Output is correct
5 Correct 72 ms 11184 KB Output is correct
6 Correct 542 ms 28080 KB Output is correct
7 Correct 226 ms 28100 KB Output is correct
8 Correct 528 ms 28560 KB Output is correct
9 Correct 253 ms 28512 KB Output is correct
10 Correct 192 ms 31896 KB Output is correct
11 Correct 271 ms 31108 KB Output is correct
12 Incorrect 37 ms 11996 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11160 KB Output is correct
2 Correct 209 ms 12980 KB Output is correct
3 Correct 87 ms 13016 KB Output is correct
4 Correct 146 ms 12996 KB Output is correct
5 Correct 80 ms 13260 KB Output is correct
6 Correct 82 ms 13032 KB Output is correct
7 Correct 47 ms 12116 KB Output is correct
8 Correct 184 ms 27836 KB Output is correct
9 Correct 205 ms 27836 KB Output is correct
10 Correct 43 ms 11976 KB Output is correct
11 Correct 204 ms 37700 KB Output is correct
12 Correct 193 ms 37644 KB Output is correct
13 Correct 201 ms 37600 KB Output is correct
14 Correct 68 ms 12020 KB Output is correct
15 Correct 547 ms 27948 KB Output is correct
16 Correct 200 ms 27980 KB Output is correct
17 Correct 564 ms 28504 KB Output is correct
18 Correct 239 ms 28452 KB Output is correct
19 Correct 210 ms 31772 KB Output is correct
20 Correct 291 ms 31124 KB Output is correct
21 Correct 198 ms 28280 KB Output is correct
22 Correct 246 ms 28512 KB Output is correct
23 Correct 271 ms 28444 KB Output is correct
24 Correct 280 ms 28760 KB Output is correct
25 Correct 226 ms 31220 KB Output is correct
26 Correct 170 ms 28492 KB Output is correct
27 Correct 179 ms 28600 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11160 KB Output is correct
2 Correct 209 ms 12980 KB Output is correct
3 Correct 87 ms 13016 KB Output is correct
4 Correct 146 ms 12996 KB Output is correct
5 Correct 80 ms 13260 KB Output is correct
6 Correct 82 ms 13032 KB Output is correct
7 Correct 47 ms 12116 KB Output is correct
8 Correct 184 ms 27836 KB Output is correct
9 Correct 205 ms 27836 KB Output is correct
10 Correct 43 ms 11976 KB Output is correct
11 Correct 204 ms 37700 KB Output is correct
12 Correct 193 ms 37644 KB Output is correct
13 Correct 201 ms 37600 KB Output is correct
14 Correct 68 ms 12020 KB Output is correct
15 Correct 547 ms 27948 KB Output is correct
16 Correct 200 ms 27980 KB Output is correct
17 Correct 564 ms 28504 KB Output is correct
18 Correct 239 ms 28452 KB Output is correct
19 Correct 210 ms 31772 KB Output is correct
20 Correct 291 ms 31124 KB Output is correct
21 Correct 198 ms 28280 KB Output is correct
22 Correct 246 ms 28512 KB Output is correct
23 Correct 271 ms 28444 KB Output is correct
24 Correct 280 ms 28760 KB Output is correct
25 Correct 226 ms 31220 KB Output is correct
26 Correct 170 ms 28492 KB Output is correct
27 Correct 179 ms 28600 KB Output is correct
28 Incorrect 58 ms 11980 KB Extra information in the output file
29 Halted 0 ms 0 KB -