oj.uz

Submission #528807

# Submission time Handle Problem Language Result Execution time Memory
528807 2022-02-21T13:33:24 Z radal Inside information (BOI21_servers) C++14
100 / 100
 607 ms 41232 KB 
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 3e5+20,mod = 998244353,inf = 1e9+10;
vector<pll> adj[N],Q1[N];
vector<int> Q2[N];
int sz[N],n,k,fen[N],ans[N],ch[N],W[N],lst[N];
bool hide[N],fl[N][2];
char c[N];
int siz(int v,int p){
    sz[v] = 1;
    for (pll u : adj[v]){
        if (hide[u.X] || u.X == p) continue;
        sz[v] += siz(u.X,v);
    }
    return sz[v];
}
inline void upd(int l,int x){
    for(; l < k; l |= (l+1))
        fen[l] += x;
}
inline int que(int r){
    int res = 0;
    for(; r >= 0; r = (r&(r+1))-1)
        res += fen[r];
    return res;
}
inline int cent(int v,int _n){
    int p = -1;
    while (true){
        bool f = 0;
        for (pll u : adj[v]){
            if (u.X == p || hide[u.X]) continue;
            if (sz[u.X]*2 > _n){
                p = v;
                v = u.X;
                f = 1;
                break;
            }
        }
        if (!f) break;
    }
    return v;
}
void dfs(int v,int w,int par){
    if (par == -1) fl[v][0] = fl[v][1] = 1;
    W[v] = w;
    for (pll p : adj[v]){
        int u = p.X;
        if (u == par || hide[u]) continue;
        if (par == -1){
            fl[u][0] = 1;
            fl[u][1] = 1;
            lst[u] = p.Y;
        }
        else{
            if (fl[v][0] && p.Y < w) fl[u][0] = 1;
            else fl[u][0] = 0;
            if (fl[v][1] && p.Y > w) fl[u][1] = 1;
            else fl[u][1] = 0;
            lst[u] = lst[v];
        }
        dfs(u,p.Y,v);
    }
}
void add(int v,int x,int p){
    if (!fl[v][1]) return;
    upd(W[v],x);
    ch[v] += x;
    for (pll u : adj[v]){
        if (u.X != p && !hide[u.X]){
            add(u.X,x,v);
        }
    }
}
void calc(int v,int p){
    if (!fl[v][0]) return;
    for(int t : Q2[v])
        ans[t] += que(t)+(lst[v] < t);
    for (pll u : Q1[v])
        if (u.X == v || (ch[u.X] && max(W[u.X],lst[v]) <= u.Y)) ans[u.Y] = 1;
    for (pll u : adj[v]){
        if (hide[u.X] || u.X == p) continue;
        calc(u.X,v);
    }
}
void decom(int v){
    v = cent(v,siz(v,-1));
    hide[v] = 1;
    ch[v] = 1;
    dfs(v,0,-1);
    for (pll u : adj[v]){
        if (hide[u.X]) continue;
        calc(u.X,v);
        add(u.X,1,v);
    }
    for (int t : Q2[v])
        ans[t] += que(t)+1;
    ch[v] = 0;
    for (pll u : Q1[v])
        if (u.X == v || (ch[u.X] && W[u.X] <= u.Y)) ans[u.Y] = 1;
    for (pll u : adj[v])
        if (!hide[u.X])
            add(u.X,-1,v);
    for (pll u : adj[v]) if (!hide[u.X]) decom(u.X);
}
int main(){
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    k += n;
    rep(i,1,k){
        int v;
        cin >> c[i] >> v;
        if (c[i] == 'S'){
            int u;
            cin >> u;
            adj[u].pb({v,i});
            adj[v].pb({u,i});
        }
        if (c[i] == 'Q'){
            int u;
            cin >> u;
            Q1[u].pb({v,i});
        }
        if (c[i] == 'C')
            Q2[v].pb(i);
    }
    rep(i,1,n+1) reverse(adj[i].begin(),adj[i].end());
    decom(1);
    rep(i,1,k){
        if (c[i] == 'S') continue;
        if (c[i] == 'Q')
            cout << ((ans[i]) ? "yes" : "no" ) << endl;
        else
            cout << ans[i] << endl;
    }
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 160 ms 24748 KB Output is correct
2 Correct 168 ms 25336 KB Output is correct
3 Correct 161 ms 25328 KB Output is correct
4 Correct 171 ms 25388 KB Output is correct
5 Correct 169 ms 25288 KB Output is correct
6 Correct 170 ms 25244 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 160 ms 24748 KB Output is correct
2 Correct 168 ms 25336 KB Output is correct
3 Correct 161 ms 25328 KB Output is correct
4 Correct 171 ms 25388 KB Output is correct
5 Correct 169 ms 25288 KB Output is correct
6 Correct 170 ms 25244 KB Output is correct
7 Correct 164 ms 25176 KB Output is correct
8 Correct 168 ms 25180 KB Output is correct
9 Correct 188 ms 25036 KB Output is correct
10 Correct 167 ms 25296 KB Output is correct
11 Correct 183 ms 24968 KB Output is correct
12 Correct 175 ms 24868 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24816 KB Output is correct
2 Correct 282 ms 33964 KB Output is correct
3 Correct 264 ms 34000 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24816 KB Output is correct
2 Correct 282 ms 33964 KB Output is correct
3 Correct 264 ms 34000 KB Output is correct
4 Correct 166 ms 25168 KB Output is correct
5 Correct 273 ms 33772 KB Output is correct
6 Correct 217 ms 32488 KB Output is correct
7 Correct 232 ms 32328 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 24676 KB Output is correct
2 Correct 396 ms 40676 KB Output is correct
3 Correct 420 ms 40732 KB Output is correct
4 Correct 338 ms 40468 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 24676 KB Output is correct
2 Correct 396 ms 40676 KB Output is correct
3 Correct 420 ms 40732 KB Output is correct
4 Correct 338 ms 40468 KB Output is correct
5 Correct 162 ms 25168 KB Output is correct
6 Correct 398 ms 41152 KB Output is correct
7 Correct 398 ms 41156 KB Output is correct
8 Correct 386 ms 40644 KB Output is correct
9 Correct 415 ms 40596 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 24792 KB Output is correct
2 Correct 336 ms 33964 KB Output is correct
3 Correct 365 ms 33944 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 24792 KB Output is correct
2 Correct 336 ms 33964 KB Output is correct
3 Correct 365 ms 33944 KB Output is correct
4 Correct 160 ms 25092 KB Output is correct
5 Correct 402 ms 34468 KB Output is correct
6 Correct 349 ms 34256 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 24748 KB Output is correct
2 Correct 413 ms 40788 KB Output is correct
3 Correct 403 ms 40708 KB Output is correct
4 Correct 337 ms 40512 KB Output is correct
5 Correct 165 ms 25072 KB Output is correct
6 Correct 328 ms 34076 KB Output is correct
7 Correct 329 ms 33972 KB Output is correct
8 Correct 361 ms 34204 KB Output is correct
9 Correct 342 ms 34756 KB Output is correct
10 Correct 478 ms 37768 KB Output is correct
11 Correct 418 ms 36552 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 24748 KB Output is correct
2 Correct 413 ms 40788 KB Output is correct
3 Correct 403 ms 40708 KB Output is correct
4 Correct 337 ms 40512 KB Output is correct
5 Correct 165 ms 25072 KB Output is correct
6 Correct 328 ms 34076 KB Output is correct
7 Correct 329 ms 33972 KB Output is correct
8 Correct 361 ms 34204 KB Output is correct
9 Correct 342 ms 34756 KB Output is correct
10 Correct 478 ms 37768 KB Output is correct
11 Correct 418 ms 36552 KB Output is correct
12 Correct 155 ms 25128 KB Output is correct
13 Correct 404 ms 41128 KB Output is correct
14 Correct 367 ms 41232 KB Output is correct
15 Correct 395 ms 40640 KB Output is correct
16 Correct 392 ms 40652 KB Output is correct
17 Correct 157 ms 25096 KB Output is correct
18 Correct 343 ms 34588 KB Output is correct
19 Correct 350 ms 34332 KB Output is correct
20 Correct 375 ms 34932 KB Output is correct
21 Correct 366 ms 35308 KB Output is correct
22 Correct 569 ms 37264 KB Output is correct
23 Correct 607 ms 37572 KB Output is correct
24 Correct 574 ms 36640 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 158 ms 24772 KB Output is correct
2 Correct 164 ms 25388 KB Output is correct
3 Correct 166 ms 25388 KB Output is correct
4 Correct 164 ms 25372 KB Output is correct
5 Correct 167 ms 25284 KB Output is correct
6 Correct 163 ms 25240 KB Output is correct
7 Correct 155 ms 25116 KB Output is correct
8 Correct 269 ms 34320 KB Output is correct
9 Correct 257 ms 33952 KB Output is correct
10 Correct 155 ms 25108 KB Output is correct
11 Correct 405 ms 40640 KB Output is correct
12 Correct 376 ms 40824 KB Output is correct
13 Correct 338 ms 40532 KB Output is correct
14 Correct 153 ms 25096 KB Output is correct
15 Correct 314 ms 33988 KB Output is correct
16 Correct 318 ms 33912 KB Output is correct
17 Correct 329 ms 34240 KB Output is correct
18 Correct 337 ms 34760 KB Output is correct
19 Correct 448 ms 37828 KB Output is correct
20 Correct 411 ms 36536 KB Output is correct
21 Correct 281 ms 34008 KB Output is correct
22 Correct 281 ms 33980 KB Output is correct
23 Correct 309 ms 34340 KB Output is correct
24 Correct 325 ms 34648 KB Output is correct
25 Correct 419 ms 38276 KB Output is correct
26 Correct 365 ms 33472 KB Output is correct
27 Correct 333 ms 33092 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 158 ms 24772 KB Output is correct
2 Correct 164 ms 25388 KB Output is correct
3 Correct 166 ms 25388 KB Output is correct
4 Correct 164 ms 25372 KB Output is correct
5 Correct 167 ms 25284 KB Output is correct
6 Correct 163 ms 25240 KB Output is correct
7 Correct 155 ms 25116 KB Output is correct
8 Correct 269 ms 34320 KB Output is correct
9 Correct 257 ms 33952 KB Output is correct
10 Correct 155 ms 25108 KB Output is correct
11 Correct 405 ms 40640 KB Output is correct
12 Correct 376 ms 40824 KB Output is correct
13 Correct 338 ms 40532 KB Output is correct
14 Correct 153 ms 25096 KB Output is correct
15 Correct 314 ms 33988 KB Output is correct
16 Correct 318 ms 33912 KB Output is correct
17 Correct 329 ms 34240 KB Output is correct
18 Correct 337 ms 34760 KB Output is correct
19 Correct 448 ms 37828 KB Output is correct
20 Correct 411 ms 36536 KB Output is correct
21 Correct 281 ms 34008 KB Output is correct
22 Correct 281 ms 33980 KB Output is correct
23 Correct 309 ms 34340 KB Output is correct
24 Correct 325 ms 34648 KB Output is correct
25 Correct 419 ms 38276 KB Output is correct
26 Correct 365 ms 33472 KB Output is correct
27 Correct 333 ms 33092 KB Output is correct
28 Correct 161 ms 25156 KB Output is correct
29 Correct 168 ms 24976 KB Output is correct
30 Correct 167 ms 24860 KB Output is correct
31 Correct 168 ms 25120 KB Output is correct
32 Correct 167 ms 24732 KB Output is correct
33 Correct 164 ms 24684 KB Output is correct
34 Correct 159 ms 24956 KB Output is correct
35 Correct 266 ms 34420 KB Output is correct
36 Correct 222 ms 32280 KB Output is correct
37 Correct 221 ms 32184 KB Output is correct
38 Correct 160 ms 24896 KB Output is correct
39 Correct 418 ms 40864 KB Output is correct
40 Correct 370 ms 41104 KB Output is correct
41 Correct 386 ms 40152 KB Output is correct
42 Correct 394 ms 40180 KB Output is correct
43 Correct 157 ms 24712 KB Output is correct
44 Correct 339 ms 33944 KB Output is correct
45 Correct 332 ms 33724 KB Output is correct
46 Correct 344 ms 34472 KB Output is correct
47 Correct 365 ms 34872 KB Output is correct
48 Correct 480 ms 36804 KB Output is correct
49 Correct 552 ms 36884 KB Output is correct
50 Correct 535 ms 35992 KB Output is correct
51 Correct 237 ms 32048 KB Output is correct
52 Correct 229 ms 31932 KB Output is correct
53 Correct 223 ms 31624 KB Output is correct
54 Correct 219 ms 31932 KB Output is correct
55 Correct 251 ms 32576 KB Output is correct
56 Correct 292 ms 33756 KB Output is correct
57 Correct 374 ms 36428 KB Output is correct
58 Correct 417 ms 32884 KB Output is correct
59 Correct 362 ms 32080 KB Output is correct