oj.uz

Submission #402429

# Submission time Handle Problem Language Result Execution time Memory
402429 2021-05-11T16:38:47 Z doowey Inside information (BOI21_servers) C++14
50 / 100
 430 ms 28108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 120100;
const int M = N * 2;
vector<pii> T[N];
vector<pii> qq[N];
int bruh[M];
int soln[M];

bool chk(int node, int par, int target, int las){
    if(node == target) return true;
    for(auto x : T[node]){
        if(x.fi == par || x.se < las) continue;
        if(chk(x.fi, node, target, x.se))
            return true;
    }
    return false;
}

int sub[N];
bool vis[N];
int dd[N];
int nani[N];
int iter;

void dfs(int u, int pp){
    sub[u]=1;
    dd[u]=iter;
    nani[u]=-1;
    for(auto x : T[u]){
        if(x.fi == pp || vis[x.fi]) continue;
        dfs(x.fi, u);
        sub[u] += sub[x.fi];
    }
}

bool ton[N];
bool fron[N];
int in[N];
int shd[N];



void dfs1(int u, int pp, int ss, int l1, int l2){
    in[u]=l2;
    nani[u]=ss;
    if(l1 == -1 || l2 == -1){
        ton[u]=true;
        fron[u]=true;
    }
    else{
        if(l1 > l2){
            fron[u] = fron[pp];
            ton[u] = false;
        }
        else{
            fron[u] = false;
            ton[u] = ton[pp];
        }
    }
    for(auto x : qq[u]){
        if(dd[u]!=dd[x.fi] || nani[u]==nani[x.fi]) continue;
        if(nani[x.fi] == -1){
            soln[x.se] = -2;
        }
        else{
            if(nani[x.fi] == 0){
                if(fron[u] && shd[ss] <= x.se){
                    soln[x.se] = -1;
                }
                else{
                    soln[x.se] = -2;
                }
            }
            else{
                if(fron[u] && ton[x.fi] && in[x.fi] <= x.se){
                    soln[x.se] = -1;
                }
                else{
                    soln[x.se] = -2;
                }
            }
        }
    }
    for(auto x : T[u]){
        if(x.fi == pp || vis[x.fi]) continue;
        dfs1(x.fi, u, ss, l2, x.se);
    }
}

bool comp(pii a, pii b){
    return a.se > b.se;
}


void decomp(int node){
    iter ++ ;
    dfs(node, -1);
    int las = -1;
    int sz = sub[node];
    bool go = true;
    while(go){
        go = false;
        for(auto x : T[node]){
            if(x.fi == las || vis[x.fi]) continue;
            if(sub[x.fi] > sz/2){
                las = node;
                node = x.fi;
                go = true;
                break;
            }
        }
    }
    fron[node]=ton[node]=true;
    nani[node] = 0;
    sort(T[node].begin(), T[node].end(), comp);
    int cc = 0;
    for(auto x : T[node]){
        if(vis[x.fi]) continue;
        cc ++ ;
        shd[cc] = x.se;
        dfs1(x.fi, node, cc, -1, x.se);
    }
    for(auto x : qq[node]){
        if(dd[node] != dd[x.fi]) continue;
        if(ton[x.fi] && in[x.fi] <= x.se){
            soln[x.se] = -1;
        }
        else{
            soln[x.se] = -2;
        }
    }
    vis[node]=true;
    for(auto x : T[node]){
        if(!vis[x.fi]) decomp(x.fi);
    }

}

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    char typ;
    int xx, yy;
    bool sol;
    for(int iq = 1; iq <= n + q - 1; iq ++ ){
        cin >> typ;
        if(typ == 'S'){
            cin >> xx >> yy;
            T[xx].push_back(mp(yy, iq));
            T[yy].push_back(mp(xx, iq));
        }
        else if(typ == 'Q'){
            cin >> xx >> yy;
            /*
            sol = chk(yy, -1, xx, 0);
            if(sol == true){
                bruh[iq] = -1;
            }
            else{
                bruh[iq] = -2;
            }
            */
            if(xx == yy)
                soln[iq] = -1;
            else
                qq[yy].push_back(mp(xx, iq));
        }
        else{
            cin >> xx;
        }
    }
    decomp(1);
    for(int i = 1; i <= n + q - 1; i ++ ){
        if(soln[i] == 0) continue;
        if(soln[i] == -1){
            cout << "yes\n";
        }
        else if(soln[i] == -2){
            cout << "no\n";
        }
        else{
            cout << soln[i] << "\n";
        }
    }
    return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:156:10: warning: unused variable 'sol' [-Wunused-variable]
  156 |     bool sol;
      |          ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8332 KB Output is correct
2 Correct 45 ms 8680 KB Output is correct
3 Correct 51 ms 8540 KB Output is correct
4 Correct 48 ms 8900 KB Output is correct
5 Correct 47 ms 9052 KB Output is correct
6 Correct 40 ms 8892 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8332 KB Output is correct
2 Correct 45 ms 8680 KB Output is correct
3 Correct 51 ms 8540 KB Output is correct
4 Correct 48 ms 8900 KB Output is correct
5 Correct 47 ms 9052 KB Output is correct
6 Correct 40 ms 8892 KB Output is correct
7 Incorrect 31 ms 8260 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 33 ms 8388 KB Output is correct
2 Correct 155 ms 18612 KB Output is correct
3 Correct 154 ms 19852 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8388 KB Output is correct
2 Correct 155 ms 18612 KB Output is correct
3 Correct 154 ms 19852 KB Output is correct
4 Incorrect 31 ms 9144 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 37 ms 8388 KB Output is correct
2 Correct 325 ms 24548 KB Output is correct
3 Correct 335 ms 24952 KB Output is correct
4 Correct 200 ms 26684 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8388 KB Output is correct
2 Correct 325 ms 24548 KB Output is correct
3 Correct 335 ms 24952 KB Output is correct
4 Correct 200 ms 26684 KB Output is correct
5 Incorrect 31 ms 9260 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 32 ms 8388 KB Output is correct
2 Correct 199 ms 17244 KB Output is correct
3 Correct 244 ms 19080 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8388 KB Output is correct
2 Correct 199 ms 17244 KB Output is correct
3 Correct 244 ms 19080 KB Output is correct
4 Incorrect 31 ms 9016 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 31 ms 8308 KB Output is correct
2 Correct 338 ms 24484 KB Output is correct
3 Correct 334 ms 24648 KB Output is correct
4 Correct 217 ms 26640 KB Output is correct
5 Correct 31 ms 9284 KB Output is correct
6 Correct 194 ms 19780 KB Output is correct
7 Correct 256 ms 19072 KB Output is correct
8 Correct 318 ms 20676 KB Output is correct
9 Correct 320 ms 20244 KB Output is correct
10 Correct 346 ms 23620 KB Output is correct
11 Correct 354 ms 22800 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8308 KB Output is correct
2 Correct 338 ms 24484 KB Output is correct
3 Correct 334 ms 24648 KB Output is correct
4 Correct 217 ms 26640 KB Output is correct
5 Correct 31 ms 9284 KB Output is correct
6 Correct 194 ms 19780 KB Output is correct
7 Correct 256 ms 19072 KB Output is correct
8 Correct 318 ms 20676 KB Output is correct
9 Correct 320 ms 20244 KB Output is correct
10 Correct 346 ms 23620 KB Output is correct
11 Correct 354 ms 22800 KB Output is correct
12 Incorrect 30 ms 9152 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 31 ms 8332 KB Output is correct
2 Correct 54 ms 8736 KB Output is correct
3 Correct 42 ms 8588 KB Output is correct
4 Correct 50 ms 8848 KB Output is correct
5 Correct 54 ms 9112 KB Output is correct
6 Correct 47 ms 8880 KB Output is correct
7 Correct 31 ms 8516 KB Output is correct
8 Correct 147 ms 18744 KB Output is correct
9 Correct 155 ms 19704 KB Output is correct
10 Correct 31 ms 9284 KB Output is correct
11 Correct 308 ms 27772 KB Output is correct
12 Correct 334 ms 28004 KB Output is correct
13 Correct 203 ms 28108 KB Output is correct
14 Correct 31 ms 9256 KB Output is correct
15 Correct 196 ms 19848 KB Output is correct
16 Correct 288 ms 19180 KB Output is correct
17 Correct 311 ms 20676 KB Output is correct
18 Correct 322 ms 20292 KB Output is correct
19 Correct 342 ms 23668 KB Output is correct
20 Correct 364 ms 22828 KB Output is correct
21 Correct 192 ms 20060 KB Output is correct
22 Correct 174 ms 19968 KB Output is correct
23 Correct 286 ms 20220 KB Output is correct
24 Correct 282 ms 20212 KB Output is correct
25 Correct 430 ms 24980 KB Output is correct
26 Correct 251 ms 18248 KB Output is correct
27 Correct 244 ms 17876 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8332 KB Output is correct
2 Correct 54 ms 8736 KB Output is correct
3 Correct 42 ms 8588 KB Output is correct
4 Correct 50 ms 8848 KB Output is correct
5 Correct 54 ms 9112 KB Output is correct
6 Correct 47 ms 8880 KB Output is correct
7 Correct 31 ms 8516 KB Output is correct
8 Correct 147 ms 18744 KB Output is correct
9 Correct 155 ms 19704 KB Output is correct
10 Correct 31 ms 9284 KB Output is correct
11 Correct 308 ms 27772 KB Output is correct
12 Correct 334 ms 28004 KB Output is correct
13 Correct 203 ms 28108 KB Output is correct
14 Correct 31 ms 9256 KB Output is correct
15 Correct 196 ms 19848 KB Output is correct
16 Correct 288 ms 19180 KB Output is correct
17 Correct 311 ms 20676 KB Output is correct
18 Correct 322 ms 20292 KB Output is correct
19 Correct 342 ms 23668 KB Output is correct
20 Correct 364 ms 22828 KB Output is correct
21 Correct 192 ms 20060 KB Output is correct
22 Correct 174 ms 19968 KB Output is correct
23 Correct 286 ms 20220 KB Output is correct
24 Correct 282 ms 20212 KB Output is correct
25 Correct 430 ms 24980 KB Output is correct
26 Correct 251 ms 18248 KB Output is correct
27 Correct 244 ms 17876 KB Output is correct
28 Incorrect 30 ms 9132 KB Extra information in the output file
29 Halted 0 ms 0 KB -