oj.uz

Submission #658633

# Submission time Handle Problem Language Result Execution time Memory
658633 2022-11-13T22:24:38 Z Lobo Inside information (BOI21_servers) C++17
100 / 100
 1110 ms 158676 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;

int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[maxn][25], pin[maxn][25], pde[maxn][25];
int dpt[maxn], dpp[maxn];
map<int,int> dp[maxn];
vector<pair<int,int>> g[maxn];

void dfs(int u, int ant) {
    for(int i = 1; i <= 20; i++) {
        if(pp[u][i-1] == -1) {
            pp[u][i] = -1;
            pmn[u][i] = pmn[u][i-1];
            pmx[u][i] = pmx[u][i-1];
            pin[u][i] = pin[u][i-1];
            pde[u][i] = pde[u][i-1];
        }
        else {
            pp[u][i] = pp[pp[u][i-1]][i-1];
            pmn[u][i] = min(pmn[u][i-1],pmn[pp[u][i-1]][i-1]);
            pmx[u][i] = max(pmx[u][i-1],pmx[pp[u][i-1]][i-1]);

            pde[u][i] = pde[u][i-1]&pde[pp[u][i-1]][i-1]&(pmn[u][i-1] > pmx[pp[u][i-1]][i-1]);
            pin[u][i] = pin[u][i-1]&pin[pp[u][i-1]][i-1]&(pmx[u][i-1] < pmn[pp[u][i-1]][i-1]);
        }
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        pmn[v][0] = w;
        pmx[v][0] = w;
        pin[v][0] = 1;
        pde[v][0] = 1;
        pp[v][0] = u;
        h[v] = h[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(h[v] > h[u]) {
        swap(u,v);
    }

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[v]) u = pp[u][i];
    }

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && pp[v][i] != -1 && pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

int qryQ(int u, int v, int w) {
    int lc = lca(u,v);
    int ans = 1;

    vector<int> ordu, ordv, ords;
    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[lc]) {
            if(pin[u][i] == 0) ans = 0;
            ordu.pb(pmn[u][i]);
            ordu.pb(pmx[u][i]);
            u = pp[u][i];
        }
    }
    for(int i = 20; i >= 0; i--) {
        if(pp[v][i] != -1 && h[pp[v][i]] >= h[lc]) {
            if(pde[v][i] == 0) ans = 0;
            ordv.pb(pmx[v][i]);
            ordv.pb(pmn[v][i]);
            v = pp[v][i];
        }
    }

    for(auto x : ordu) ords.pb(x);
    reverse(all(ordv));
    for(auto x : ordv) ords.pb(x);

    for(int i = 0; i < ords.size(); i++) {
        if(ords[i] > w) ans = 0;
        if(i != 0 && ords[i] < ords[i-1]) ans = 0;
    }
    return ans;
}

int szct[maxn], block[maxn], lvlct[maxn], parct[maxn];
int inc[25][maxn], dcr[25][maxn], idct[25][maxn], prevct[25][maxn], prevctw[25][maxn];
vector<int> pass, bit[maxn];
void dfsszct(int u, int ant) {
    pass.pb(u);
    szct[u] = 1;
    for(auto V : g[u]) if(!block[V.fr] && V.fr != ant) {
        int v = V.fr;
        dfsszct(v,u);
        szct[u]+= szct[v];
    }
}

void dfsct(int u, int ant, int antw, int lvlcur) {
    for(auto V : g[u]) if(!block[V.fr] && V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        inc[lvlcur][v] = inc[lvlcur][u]&(w > antw);
        dcr[lvlcur][v] = dcr[lvlcur][u]&(w < antw);
        idct[lvlcur][v] = idct[lvlcur][u];
        prevct[lvlcur][v] = u;
        prevctw[lvlcur][v] = prevctw[lvlcur][u];
        dfsct(v,u,w,lvlcur);
    }
}

int buildcentroid(int rt, int lvlcur) {
    pass.clear();
    dfsszct(rt,0);

    int ct;
    for(auto u : pass) {
        bool okct = true;
        if(szct[rt]-szct[u] > szct[rt]/2) okct = false;
        for(auto V : g[u]) if(!block[V.fr] && szct[V.fr] < szct[u]) {
            int v = V.fr;
            if(szct[v] > szct[rt]/2) okct = false;
        }

        if(okct) {
            ct = u;
            break;
        }
    }

    block[ct] = 1;
    lvlct[ct] = lvlcur;

    vector<pair<int,int>> ord;
    for(auto V : g[ct]) if(!block[V.fr]) {
        int v = V.fr;
        int w = V.sc;
        ord.pb(mp(w,v));
    }
    sort(all(ord),greater<pair<int,int>>());
    bit[ct].resize((int) ord.size()+1,0);
    idct[lvlcur][ct] = ord.size()+1;
    inc[lvlcur][ct] = 1;
    dcr[lvlcur][ct] = 1;
    prevctw[lvlcur][ct] = 0;

    for(int i = 1; i <= ord.size(); i++) {
        int v = ord[i-1].sc;
        int w = ord[i-1].fr;
        inc[lvlcur][v] = 1;
        dcr[lvlcur][v] = 1;
        idct[lvlcur][v] = i;
        prevct[lvlcur][v] = ct;
        prevctw[lvlcur][v] = w;
        dfsct(v,0,w,lvlcur);
    }

    for(auto V : g[ct]) if(!block[V.fr]) {
        int v = V.fr;
        parct[buildcentroid(v,lvlcur+1)] = ct;
    }
    return ct;
}

void updbit(int ct, int pos, int val) {
    for(int i = pos; i < bit[ct].size(); i+= i&-i) {
        bit[ct][i]+= val;
    }
}
int qrybit(int ct, int pos) {
    int val = 0;
    for(int i = pos; i > 0; i-= i&-i) {
        val+= bit[ct][i];
    }
    return val+1;
}

int32_t main() {
    // freopen("in.in", "r", stdin);
    cin >> n >> k;
    vector<pair<pair<int,int>,pair<int,int>>> qrys;
    for(int i = 1; i <= n+k-1; i++) {
        char op; cin >> op;
        if(op == 'S') {
            int u,v;cin >> u >> v;
            g[u].pb(mp(v,i));
            g[v].pb(mp(u,i));
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(1,i),mp(u,v)));
        }
        else if(op == 'C') {
            int v; cin >> v;
            qrys.pb(mp(mp(2,i),mp(v,0)));
        }
    }

    buildcentroid(1,0);

    pp[1][0] = -1;
    pmn[1][0] = inf;
    pmx[1][0] = -inf;
    pin[1][0] = 1;
    pde[1][0] = 1;
    dfs(1,1);

    for(int i = 1; i <= n; i++) {
        dpt[i] = 1;
        dpp[i] = 0;
        dp[i][n+k] = 1;
    }

    for(auto X : qrys) {
        int optp = X.fr.fr;
        if(optp == 0) {
            int u = X.sc.fr;
            int v = X.sc.sc;
            int ct,lvl;
            ct = v;
            lvl = lvlct[ct];
            while(lvl != -1) {
                if(prevct[lvl][v] == u) {
                    if(inc[lvl][v]) {
                        updbit(ct,idct[lvl][v],1);
                    }
                }
                ct = parct[ct];
                lvl--;
            }

            ct = u;
            lvl = lvlct[ct];
            while(lvl != -1) {
                if(prevct[lvl][u] == v) {
                    if(inc[lvl][u]) {
                        updbit(ct,idct[lvl][u],1);
                    }
                }
                ct = parct[ct];
                lvl--;
            }
        }
        if(optp == 2) {
            int v = X.sc.fr;
            int w = X.fr.sc;
            int ct,lvl;
            int ans = 0;
            ct = v;
            lvl = lvlct[v];
            while(lvl != -1) {
                if(dcr[lvl][v] && prevctw[lvl][v] <= w) {
                    ans+= qrybit(ct,idct[lvl][v]-1);

                }
                ct = parct[ct];
                lvl--;
            }
            cout << ans << endl;
        }
        if(optp == 1) {
            int w = X.fr.sc;
            int u = X.sc.sc;
            int v = X.sc.fr;
            if(qryQ(u,v,w)) cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }

}

Compilation message

servers.cpp: In function 'int qryQ(int, int, int)':
servers.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i < ords.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
servers.cpp: In function 'int buildcentroid(int, int)':
servers.cpp:164:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int i = 1; i <= ord.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
servers.cpp: In function 'void updbit(int, int, int)':
servers.cpp:183:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int i = pos; i < bit[ct].size(); i+= i&-i) {
      |                      ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'int buildcentroid(int, int)':
servers.cpp:133:9: warning: 'ct' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     int ct;
      |         ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 283 ms 31100 KB Output is correct
2 Correct 338 ms 35292 KB Output is correct
3 Correct 332 ms 34792 KB Output is correct
4 Correct 422 ms 35464 KB Output is correct
5 Correct 401 ms 35828 KB Output is correct
6 Correct 316 ms 34616 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 283 ms 31100 KB Output is correct
2 Correct 338 ms 35292 KB Output is correct
3 Correct 332 ms 34792 KB Output is correct
4 Correct 422 ms 35464 KB Output is correct
5 Correct 401 ms 35828 KB Output is correct
6 Correct 316 ms 34616 KB Output is correct
7 Correct 280 ms 31628 KB Output is correct
8 Correct 303 ms 35224 KB Output is correct
9 Correct 272 ms 34724 KB Output is correct
10 Correct 345 ms 35408 KB Output is correct
11 Correct 361 ms 35636 KB Output is correct
12 Correct 317 ms 34496 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 275 ms 30964 KB Output is correct
2 Correct 650 ms 114840 KB Output is correct
3 Correct 621 ms 114932 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 275 ms 30964 KB Output is correct
2 Correct 650 ms 114840 KB Output is correct
3 Correct 621 ms 114932 KB Output is correct
4 Correct 274 ms 31544 KB Output is correct
5 Correct 522 ms 114960 KB Output is correct
6 Correct 411 ms 115276 KB Output is correct
7 Correct 404 ms 115136 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 31048 KB Output is correct
2 Correct 844 ms 158300 KB Output is correct
3 Correct 848 ms 158472 KB Output is correct
4 Correct 757 ms 158572 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 31048 KB Output is correct
2 Correct 844 ms 158300 KB Output is correct
3 Correct 848 ms 158472 KB Output is correct
4 Correct 757 ms 158572 KB Output is correct
5 Correct 257 ms 31688 KB Output is correct
6 Correct 850 ms 158320 KB Output is correct
7 Correct 741 ms 158464 KB Output is correct
8 Correct 760 ms 158260 KB Output is correct
9 Correct 747 ms 158264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 31128 KB Output is correct
2 Correct 688 ms 145440 KB Output is correct
3 Correct 721 ms 145588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 31128 KB Output is correct
2 Correct 688 ms 145440 KB Output is correct
3 Correct 721 ms 145588 KB Output is correct
4 Correct 278 ms 31804 KB Output is correct
5 Correct 599 ms 145148 KB Output is correct
6 Correct 677 ms 145180 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 293 ms 31132 KB Output is correct
2 Correct 786 ms 158640 KB Output is correct
3 Correct 815 ms 158656 KB Output is correct
4 Correct 809 ms 158676 KB Output is correct
5 Correct 396 ms 31772 KB Output is correct
6 Correct 613 ms 145408 KB Output is correct
7 Correct 690 ms 145724 KB Output is correct
8 Correct 908 ms 146404 KB Output is correct
9 Correct 856 ms 145656 KB Output is correct
10 Correct 1024 ms 154100 KB Output is correct
11 Correct 1110 ms 153208 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 293 ms 31132 KB Output is correct
2 Correct 786 ms 158640 KB Output is correct
3 Correct 815 ms 158656 KB Output is correct
4 Correct 809 ms 158676 KB Output is correct
5 Correct 396 ms 31772 KB Output is correct
6 Correct 613 ms 145408 KB Output is correct
7 Correct 690 ms 145724 KB Output is correct
8 Correct 908 ms 146404 KB Output is correct
9 Correct 856 ms 145656 KB Output is correct
10 Correct 1024 ms 154100 KB Output is correct
11 Correct 1110 ms 153208 KB Output is correct
12 Correct 267 ms 32028 KB Output is correct
13 Correct 784 ms 158448 KB Output is correct
14 Correct 695 ms 158512 KB Output is correct
15 Correct 782 ms 158348 KB Output is correct
16 Correct 900 ms 158396 KB Output is correct
17 Correct 267 ms 32048 KB Output is correct
18 Correct 573 ms 145212 KB Output is correct
19 Correct 642 ms 145260 KB Output is correct
20 Correct 889 ms 146852 KB Output is correct
21 Correct 838 ms 145780 KB Output is correct
22 Correct 920 ms 152496 KB Output is correct
23 Correct 991 ms 153896 KB Output is correct
24 Correct 957 ms 153764 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 286 ms 31024 KB Output is correct
2 Correct 323 ms 35012 KB Output is correct
3 Correct 286 ms 34512 KB Output is correct
4 Correct 351 ms 35196 KB Output is correct
5 Correct 305 ms 35384 KB Output is correct
6 Correct 270 ms 34120 KB Output is correct
7 Correct 231 ms 31272 KB Output is correct
8 Correct 578 ms 114476 KB Output is correct
9 Correct 520 ms 114488 KB Output is correct
10 Correct 244 ms 31392 KB Output is correct
11 Correct 842 ms 158180 KB Output is correct
12 Correct 790 ms 158272 KB Output is correct
13 Correct 695 ms 158128 KB Output is correct
14 Correct 259 ms 31340 KB Output is correct
15 Correct 607 ms 144716 KB Output is correct
16 Correct 736 ms 144732 KB Output is correct
17 Correct 1088 ms 145352 KB Output is correct
18 Correct 831 ms 144664 KB Output is correct
19 Correct 1084 ms 152968 KB Output is correct
20 Correct 1107 ms 152268 KB Output is correct
21 Correct 633 ms 117076 KB Output is correct
22 Correct 645 ms 117816 KB Output is correct
23 Correct 698 ms 134628 KB Output is correct
24 Correct 734 ms 132408 KB Output is correct
25 Correct 888 ms 154920 KB Output is correct
26 Correct 697 ms 142332 KB Output is correct
27 Correct 705 ms 142640 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 286 ms 31024 KB Output is correct
2 Correct 323 ms 35012 KB Output is correct
3 Correct 286 ms 34512 KB Output is correct
4 Correct 351 ms 35196 KB Output is correct
5 Correct 305 ms 35384 KB Output is correct
6 Correct 270 ms 34120 KB Output is correct
7 Correct 231 ms 31272 KB Output is correct
8 Correct 578 ms 114476 KB Output is correct
9 Correct 520 ms 114488 KB Output is correct
10 Correct 244 ms 31392 KB Output is correct
11 Correct 842 ms 158180 KB Output is correct
12 Correct 790 ms 158272 KB Output is correct
13 Correct 695 ms 158128 KB Output is correct
14 Correct 259 ms 31340 KB Output is correct
15 Correct 607 ms 144716 KB Output is correct
16 Correct 736 ms 144732 KB Output is correct
17 Correct 1088 ms 145352 KB Output is correct
18 Correct 831 ms 144664 KB Output is correct
19 Correct 1084 ms 152968 KB Output is correct
20 Correct 1107 ms 152268 KB Output is correct
21 Correct 633 ms 117076 KB Output is correct
22 Correct 645 ms 117816 KB Output is correct
23 Correct 698 ms 134628 KB Output is correct
24 Correct 734 ms 132408 KB Output is correct
25 Correct 888 ms 154920 KB Output is correct
26 Correct 697 ms 142332 KB Output is correct
27 Correct 705 ms 142640 KB Output is correct
28 Correct 255 ms 31696 KB Output is correct
29 Correct 276 ms 35084 KB Output is correct
30 Correct 236 ms 34752 KB Output is correct
31 Correct 283 ms 35320 KB Output is correct
32 Correct 261 ms 35520 KB Output is correct
33 Correct 237 ms 34360 KB Output is correct
34 Correct 247 ms 31672 KB Output is correct
35 Correct 543 ms 114852 KB Output is correct
36 Correct 371 ms 114908 KB Output is correct
37 Correct 399 ms 114760 KB Output is correct
38 Correct 241 ms 31816 KB Output is correct
39 Correct 749 ms 158508 KB Output is correct
40 Correct 694 ms 158504 KB Output is correct
41 Correct 714 ms 158012 KB Output is correct
42 Correct 703 ms 158136 KB Output is correct
43 Correct 247 ms 31624 KB Output is correct
44 Correct 543 ms 145244 KB Output is correct
45 Correct 656 ms 145308 KB Output is correct
46 Correct 839 ms 146992 KB Output is correct
47 Correct 824 ms 145896 KB Output is correct
48 Correct 892 ms 152368 KB Output is correct
49 Correct 997 ms 154184 KB Output is correct
50 Correct 1028 ms 154004 KB Output is correct
51 Correct 418 ms 117436 KB Output is correct
52 Correct 411 ms 115888 KB Output is correct
53 Correct 391 ms 114896 KB Output is correct
54 Correct 404 ms 115752 KB Output is correct
55 Correct 413 ms 117232 KB Output is correct
56 Correct 598 ms 134412 KB Output is correct
57 Correct 774 ms 154364 KB Output is correct
58 Correct 739 ms 143108 KB Output is correct
59 Correct 658 ms 141804 KB Output is correct