oj.uz

Submission #399275

# Submission time Handle Problem Language Result Execution time Memory
399275 2021-05-05T13:53:58 Z egekabas Inside information (BOI21_servers) C++14
100 / 100
 648 ms 80692 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int imp;//delete later
int n, k;
    
char t[240009];
int x[240009];
int y[240009];
    
vector<pii> g[120009];
    
int dad[120009][25];
int depth[120009];
    
int pval[120009][25];
int incr[120009][25];
int decr[120009][25];
    
void dfs(int v, int prt){
    dad[v][0] = prt;
    depth[v] = depth[prt]+1;
    
    for(int i = 1; i < 25; ++i){
        dad[v][i] = dad[dad[v][i-1]][i-1];
        pval[v][i] = pval[dad[v][i-1]][i-1];
        if(incr[v][i-1] && incr[dad[v][i-1]][i-1] && pval[v][i-1] < pval[dad[v][i-1]][0])
            incr[v][i] = 1;
        if(decr[v][i-1] && decr[dad[v][i-1]][i-1] && pval[v][i-1] > pval[dad[v][i-1]][0])
            decr[v][i] = 1;
    }
    for(auto u : g[v])
        if(u.ff != prt){
            incr[u.ff][0] = decr[u.ff][0] = 1;
            pval[u.ff][0] = u.ss;
            dfs(u.ff, v);
        }
}
int lca(int x, int y){
    if(depth[y] > depth[x])
        swap(x, y);
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(int i = 24; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
struct retst{
    int incr = 1, decr = 1, maxi = -1, last = -1;
};
retst goup(int x, int y){
    retst ret = retst();
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y]){
            if((ret.last != -1 && ret.last > pval[x][0]) || incr[x][i] == 0)
                ret.incr = 0;
            if((ret.last != -1 && ret.last < pval[x][0]) || decr[x][i] == 0)
                ret.decr = 0;
            ret.maxi = max({ret.maxi, pval[x][0], pval[x][i]});
            ret.last = pval[x][i];
            x = dad[x][i];
        }
    return ret;
}
int bit[240009];
void upd(int idx, int val){
    for(++idx; idx <= 240000; idx += idx&(-idx))
        bit[idx] += val;
}
int get(int idx){
    int ret = 0;
    for(++idx; idx > 0; idx -= idx&(-idx))
        ret += bit[idx];
    return ret;
}
vector<int> qu[240009];
int ans[240009];
int sz[240009];
int block[240009];
void getsz(int v, int prt){
    sz[v] = 1+qu[v].size();
    for(auto u : g[v]){
        if(u.ff == prt || block[u.ff]) continue;
        getsz(u.ff, v);
        sz[v] += sz[u.ff];
    }
}
int getcentroid(int v, int prt, int totsz){
    for(auto u : g[v]){
        if(u.ff == prt || block[u.ff]) continue;
        if(sz[u.ff]*2 > totsz)
            return getcentroid(u.ff, v, totsz);
    }
    return v;
}
void getvec(int v, int prt, int cur, vector<pii>&vec, int inc){
    vec.pb({v, cur});
    for(auto u : g[v]){
        if(u.ff == prt || block[u.ff]) continue;
        if(u.ss > cur && inc)
            getvec(u.ff, v, u.ss, vec, inc);
        if(u.ss < cur && !inc)
            getvec(u.ff, v, u.ss, vec, inc);
    }
}
void calc(int root){
    getsz(root, 0);
    root = getcentroid(root, 0, sz[root]);
    vector<pair<int, vector<pii>>> vinc;
    vector<pair<int, vector<pii>>> vdec;
    
    for(auto u : g[root]){
        if(block[u.ff]) continue;
        vector<pii> v1, v2;
        getvec(u.ff, root, u.ss, v1, 1);
        getvec(u.ff, root, u.ss, v2, 0);
        vinc.pb({u.ss, v1});
        vdec.pb({u.ss, v2});
    }
    sort(all(vinc));
    sort(all(vdec));
    
    for(int i = vinc.size()-1; i >= 0; --i){
        for(auto u : vdec[i].ss)
            for(auto u2 : qu[u.ff]){
                ans[u2] += get(u2);
                if(vinc[i].ff < u2)
                    ans[u2]++;
            }
        for(auto u : vinc[i].ss)
            upd(u.ss, 1);
    }
    for(auto u : qu[root])
        ans[u] += get(u);
    
    for(int i = vinc.size()-1; i >= 0; --i)
        for(auto u : vinc[i].ss)
            upd(u.ss, -1);
    
    block[root] = 1;
    for(auto u : g[root])
        if(block[u.ff] == 0)
            calc(u.ff);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> k;
    for(int i = 0; i < n+k-1; ++i){
        cin >> t[i];
        if(t[i] == 'C'){
            cin >> x[i];
            qu[x[i]].pb(i);
        }
        else
            cin >> x[i] >> y[i];
        if(t[i] == 'S'){
            g[x[i]].pb({y[i], i});
            g[y[i]].pb({x[i], i});
        }
    }
    calc(1);
    dfs(1, 0);
    for(int i = 0; i < n+k-1; ++i){
        if(t[i] == 'S') continue;
        else if(t[i] == 'Q'){
            int lc = lca(x[i], y[i]);
            retst a = goup(x[i], lc);
            retst b = goup(y[i], lc);
            if(a.decr && b.incr && (a.last == -1 || b.last == -1 || a.last > b.last) && max(a.maxi, b.maxi) <= i)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else{
            cout << ans[i]+1 << '\n';
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10564 KB Output is correct
2 Correct 99 ms 12420 KB Output is correct
3 Correct 106 ms 12804 KB Output is correct
4 Correct 119 ms 12620 KB Output is correct
5 Correct 103 ms 12352 KB Output is correct
6 Correct 94 ms 12416 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10564 KB Output is correct
2 Correct 99 ms 12420 KB Output is correct
3 Correct 106 ms 12804 KB Output is correct
4 Correct 119 ms 12620 KB Output is correct
5 Correct 103 ms 12352 KB Output is correct
6 Correct 94 ms 12416 KB Output is correct
7 Correct 69 ms 10880 KB Output is correct
8 Correct 79 ms 14464 KB Output is correct
9 Correct 66 ms 14804 KB Output is correct
10 Correct 90 ms 14584 KB Output is correct
11 Correct 80 ms 14408 KB Output is correct
12 Correct 65 ms 14412 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10492 KB Output is correct
2 Correct 374 ms 72732 KB Output is correct
3 Correct 341 ms 72816 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10492 KB Output is correct
2 Correct 374 ms 72732 KB Output is correct
3 Correct 341 ms 72816 KB Output is correct
4 Correct 67 ms 10908 KB Output is correct
5 Correct 307 ms 76624 KB Output is correct
6 Correct 233 ms 76192 KB Output is correct
7 Correct 251 ms 76412 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10564 KB Output is correct
2 Correct 435 ms 73764 KB Output is correct
3 Correct 421 ms 73792 KB Output is correct
4 Correct 506 ms 75284 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10564 KB Output is correct
2 Correct 435 ms 73764 KB Output is correct
3 Correct 421 ms 73792 KB Output is correct
4 Correct 506 ms 75284 KB Output is correct
5 Correct 66 ms 10776 KB Output is correct
6 Correct 453 ms 79060 KB Output is correct
7 Correct 471 ms 80580 KB Output is correct
8 Correct 402 ms 79488 KB Output is correct
9 Correct 388 ms 79428 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10564 KB Output is correct
2 Correct 386 ms 66476 KB Output is correct
3 Correct 338 ms 65732 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10564 KB Output is correct
2 Correct 386 ms 66476 KB Output is correct
3 Correct 338 ms 65732 KB Output is correct
4 Correct 67 ms 10872 KB Output is correct
5 Correct 328 ms 71840 KB Output is correct
6 Correct 356 ms 70400 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10564 KB Output is correct
2 Correct 381 ms 73788 KB Output is correct
3 Correct 374 ms 73704 KB Output is correct
4 Correct 460 ms 75392 KB Output is correct
5 Correct 69 ms 10564 KB Output is correct
6 Correct 353 ms 66436 KB Output is correct
7 Correct 322 ms 65732 KB Output is correct
8 Correct 469 ms 65744 KB Output is correct
9 Correct 426 ms 66136 KB Output is correct
10 Correct 531 ms 71636 KB Output is correct
11 Correct 638 ms 70620 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10564 KB Output is correct
2 Correct 381 ms 73788 KB Output is correct
3 Correct 374 ms 73704 KB Output is correct
4 Correct 460 ms 75392 KB Output is correct
5 Correct 69 ms 10564 KB Output is correct
6 Correct 353 ms 66436 KB Output is correct
7 Correct 322 ms 65732 KB Output is correct
8 Correct 469 ms 65744 KB Output is correct
9 Correct 426 ms 66136 KB Output is correct
10 Correct 531 ms 71636 KB Output is correct
11 Correct 638 ms 70620 KB Output is correct
12 Correct 67 ms 11032 KB Output is correct
13 Correct 380 ms 79040 KB Output is correct
14 Correct 428 ms 80692 KB Output is correct
15 Correct 358 ms 79496 KB Output is correct
16 Correct 380 ms 79464 KB Output is correct
17 Correct 68 ms 11716 KB Output is correct
18 Correct 316 ms 71756 KB Output is correct
19 Correct 320 ms 70348 KB Output is correct
20 Correct 414 ms 70972 KB Output is correct
21 Correct 414 ms 71424 KB Output is correct
22 Correct 548 ms 75656 KB Output is correct
23 Correct 643 ms 75396 KB Output is correct
24 Correct 600 ms 74436 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10564 KB Output is correct
2 Correct 94 ms 12560 KB Output is correct
3 Correct 82 ms 12744 KB Output is correct
4 Correct 114 ms 12584 KB Output is correct
5 Correct 98 ms 12248 KB Output is correct
6 Correct 81 ms 12376 KB Output is correct
7 Correct 68 ms 10568 KB Output is correct
8 Correct 295 ms 72792 KB Output is correct
9 Correct 297 ms 72860 KB Output is correct
10 Correct 65 ms 10528 KB Output is correct
11 Correct 378 ms 73796 KB Output is correct
12 Correct 382 ms 73876 KB Output is correct
13 Correct 454 ms 75348 KB Output is correct
14 Correct 69 ms 10564 KB Output is correct
15 Correct 354 ms 66420 KB Output is correct
16 Correct 339 ms 65732 KB Output is correct
17 Correct 481 ms 65848 KB Output is correct
18 Correct 425 ms 66244 KB Output is correct
19 Correct 517 ms 71640 KB Output is correct
20 Correct 636 ms 70556 KB Output is correct
21 Correct 314 ms 73236 KB Output is correct
22 Correct 329 ms 71020 KB Output is correct
23 Correct 366 ms 66344 KB Output is correct
24 Correct 375 ms 66376 KB Output is correct
25 Correct 465 ms 73872 KB Output is correct
26 Correct 397 ms 65808 KB Output is correct
27 Correct 389 ms 66484 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10564 KB Output is correct
2 Correct 94 ms 12560 KB Output is correct
3 Correct 82 ms 12744 KB Output is correct
4 Correct 114 ms 12584 KB Output is correct
5 Correct 98 ms 12248 KB Output is correct
6 Correct 81 ms 12376 KB Output is correct
7 Correct 68 ms 10568 KB Output is correct
8 Correct 295 ms 72792 KB Output is correct
9 Correct 297 ms 72860 KB Output is correct
10 Correct 65 ms 10528 KB Output is correct
11 Correct 378 ms 73796 KB Output is correct
12 Correct 382 ms 73876 KB Output is correct
13 Correct 454 ms 75348 KB Output is correct
14 Correct 69 ms 10564 KB Output is correct
15 Correct 354 ms 66420 KB Output is correct
16 Correct 339 ms 65732 KB Output is correct
17 Correct 481 ms 65848 KB Output is correct
18 Correct 425 ms 66244 KB Output is correct
19 Correct 517 ms 71640 KB Output is correct
20 Correct 636 ms 70556 KB Output is correct
21 Correct 314 ms 73236 KB Output is correct
22 Correct 329 ms 71020 KB Output is correct
23 Correct 366 ms 66344 KB Output is correct
24 Correct 375 ms 66376 KB Output is correct
25 Correct 465 ms 73872 KB Output is correct
26 Correct 397 ms 65808 KB Output is correct
27 Correct 389 ms 66484 KB Output is correct
28 Correct 69 ms 10820 KB Output is correct
29 Correct 76 ms 14528 KB Output is correct
30 Correct 64 ms 14780 KB Output is correct
31 Correct 89 ms 14668 KB Output is correct
32 Correct 77 ms 14368 KB Output is correct
33 Correct 62 ms 14468 KB Output is correct
34 Correct 66 ms 11732 KB Output is correct
35 Correct 286 ms 76644 KB Output is correct
36 Correct 201 ms 76136 KB Output is correct
37 Correct 211 ms 76284 KB Output is correct
38 Correct 65 ms 11728 KB Output is correct
39 Correct 384 ms 79000 KB Output is correct
40 Correct 430 ms 80512 KB Output is correct
41 Correct 368 ms 79504 KB Output is correct
42 Correct 373 ms 79404 KB Output is correct
43 Correct 69 ms 11716 KB Output is correct
44 Correct 317 ms 71784 KB Output is correct
45 Correct 316 ms 70340 KB Output is correct
46 Correct 408 ms 70980 KB Output is correct
47 Correct 410 ms 71692 KB Output is correct
48 Correct 546 ms 75748 KB Output is correct
49 Correct 648 ms 75432 KB Output is correct
50 Correct 582 ms 74368 KB Output is correct
51 Correct 228 ms 77812 KB Output is correct
52 Correct 217 ms 77108 KB Output is correct
53 Correct 216 ms 76684 KB Output is correct
54 Correct 209 ms 77384 KB Output is correct
55 Correct 217 ms 77496 KB Output is correct
56 Correct 334 ms 70604 KB Output is correct
57 Correct 368 ms 77556 KB Output is correct
58 Correct 439 ms 71316 KB Output is correct
59 Correct 400 ms 70448 KB Output is correct