oj.uz

Submission #429299

# Submission time Handle Problem Language Result Execution time Memory
429299 2021-06-15T20:15:56 Z keko37 Inside information (BOI21_servers) C++14
50 / 100
 2111 ms 56068 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 250005;

int n, k, cnt;
char tip[MAXN];
int qa[MAXN], qb[MAXN], sol[MAXN];
int server_node[MAXN];
int lo[MAXN], hi[MAXN], hi2[MAXN];
vector <pi> v[MAXN];
vector <int> q[MAXN];

void add_edge (int a, int b) {
    v[a].push_back({b, 0});
    v[b].push_back({a, 1});
}

void preseli (int i, int ind, int a, int b) {
    if (hi[a] == n + k) hi[a] = i; else hi2[a] = i;
    server_node[ind] = b;
}

int cen[MAXN], siz[MAXN], par[MAXN], upp[MAXN], dwn[MAXN], col[MAXN];
int fen[MAXN];

void ubaci (int x, int k) {
    for (x++; x < MAXN; x += x&-x) fen[x] += k;
}

int upit (int x) {
    int res = 0;
    for (x++; x > 0; x -= x&-x) res += fen[x];
    return res;
}

void upd (int node, int flg) {
    ubaci(lo[node], flg * 2);
    ubaci(hi[node], -flg);
    ubaci(hi2[node], -flg);
}

void dfs (int x, int rod) {
    if (rod == 0) upp[x] = dwn[x] = 0;
    par[x] = rod;
    siz[x] = 1;
    for (auto pp : v[x]) {
        int sus = pp.first, w = pp.second;
        if (sus == rod || cen[sus]) continue;
        dwn[sus] = w + dwn[x];
        upp[sus] = (1 - w) + upp[x];
        dfs(sus, x);
        siz[x] += siz[sus];
    }
}

int nadi_centroid (int x, int root) {
    int mx = 0, ind = -1;
    for (auto pp : v[x]) {
        int sus = pp.first, w = pp.second;
        if (sus == par[x] || cen[sus]) continue;
        if (siz[sus] > mx) {
            mx = siz[sus];
            ind = sus;
        }
    }
    if (mx * 2 <= siz[root]) return x;
    return nadi_centroid(ind, root);
}

void oboji (int x, int pred, int flg) {
    if (flg != 0 && dwn[x] == 0 && x > n) upd(x, flg);
    col[x] = pred;
    for (auto pp : v[x]) {
        int sus = pp.first, w = pp.second;
        if (sus == par[x] || cen[sus]) continue;
        oboji(sus, pred, flg);
    }
}

void decompose (int x) {
    dfs(x, 0);
    int root = nadi_centroid(x, x);
    dfs(root, 0);
    cen[root] = 1;
    swap(q[root], q[x]);
    //cout << "root je " << root << endl;

    col[root] = root;
    if (root > n) upd(root, 1);
    for (auto pp : v[root]) {
        int sus = pp.first, w = pp.second;
        if (cen[sus]) continue;
        oboji(sus, sus, 1);
    }

    for (auto i : q[root]) {
        //cout << "upit " << i << endl;
        if (tip[i] == 'Q') {
            if (col[qa[i]] != col[qb[i]]) {
                sol[i] = upp[qb[i]] + dwn[qa[i]];
            } else {
                //cout << "premjesti " << col[qa[i]] << " " << i << endl;
                q[col[qa[i]]].push_back(i);
            }
        } else {
            //cout << "premjesti " << col[qa[i]] << " " << i << endl;
            q[col[qa[i]]].push_back(i);
        }
    }

    for (auto pp : v[root]) {
        int sus = pp.first, w = pp.second;
        if (cen[sus]) continue;
        oboji(sus, sus, -1);
        for (auto i : q[sus]) {
            if (tip[i] == 'C' && upp[qa[i]] == 0) {
                int val = upit(i);
                //cout << "add " << sus << " " << i << " " << val << endl;
                sol[i] += val;
            }
        }
        oboji(sus, sus, 1);
    }

    if (root > n) upd(root, -1);
    for (auto pp : v[root]) {
        int sus = pp.first, w = pp.second;
        if (cen[sus]) continue;
        oboji(sus, sus, -1);
    }

    //return;
    for (auto pp : v[root]) {
        int sus = pp.first, w = pp.second;
        if (cen[sus]) continue;
        decompose(sus);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    cnt = n;
    for (int i = 1; i <= n; i++) {
        server_node[i] = i;
        lo[i] = 0;
        hi[i] = n + k;
        hi2[i] = n + k;
    }
    for (int i = 1; i <= n + k - 1; i++) {
        cin >> tip[i];
        if (tip[i] == 'S') {
            cin >> qa[i] >> qb[i];
            cnt++;
            lo[cnt] = i;
            hi[cnt] = n + k;
            hi2[cnt] = n + k;
            add_edge(server_node[qa[i]], cnt);
            add_edge(server_node[qb[i]], cnt);
            preseli(i, qa[i], server_node[qa[i]], cnt);
            preseli(i, qb[i], server_node[qb[i]], cnt);
        } else if (tip[i] == 'Q') {
            cin >> qa[i] >> qb[i];
            qa[i] = server_node[qa[i]];
            q[1].push_back(i);
        } else {
            cin >> qa[i];
            q[1].push_back(i);
        }
    }
    decompose(1);
    for (int i = 1; i <= n + k - 1; i++) {
        if (tip[i] == 'Q') {
            if (sol[i] == 0) cout << "yes\n"; else cout << "no\n";
        } else if (tip[i] == 'C') {
            cout << sol[i] << '\n';
        }
    }
    return 0;
}

Compilation message

servers.cpp: In function 'int nadi_centroid(int, int)':
servers.cpp:64:29: warning: unused variable 'w' [-Wunused-variable]
   64 |         int sus = pp.first, w = pp.second;
      |                             ^
servers.cpp: In function 'void oboji(int, int, int)':
servers.cpp:79:29: warning: unused variable 'w' [-Wunused-variable]
   79 |         int sus = pp.first, w = pp.second;
      |                             ^
servers.cpp: In function 'void decompose(int)':
servers.cpp:96:29: warning: unused variable 'w' [-Wunused-variable]
   96 |         int sus = pp.first, w = pp.second;
      |                             ^
servers.cpp:117:29: warning: unused variable 'w' [-Wunused-variable]
  117 |         int sus = pp.first, w = pp.second;
      |                             ^
servers.cpp:132:29: warning: unused variable 'w' [-Wunused-variable]
  132 |         int sus = pp.first, w = pp.second;
      |                             ^
servers.cpp:139:29: warning: unused variable 'w' [-Wunused-variable]
  139 |         int sus = pp.first, w = pp.second;
      |                             ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16068 KB Output is correct
2 Correct 54 ms 17348 KB Output is correct
3 Correct 71 ms 19296 KB Output is correct
4 Correct 58 ms 17580 KB Output is correct
5 Correct 63 ms 17632 KB Output is correct
6 Correct 60 ms 17888 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16068 KB Output is correct
2 Correct 54 ms 17348 KB Output is correct
3 Correct 71 ms 19296 KB Output is correct
4 Correct 58 ms 17580 KB Output is correct
5 Correct 63 ms 17632 KB Output is correct
6 Correct 60 ms 17888 KB Output is correct
7 Incorrect 38 ms 16224 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 45 ms 16192 KB Output is correct
2 Correct 1084 ms 48776 KB Output is correct
3 Correct 1159 ms 48772 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16192 KB Output is correct
2 Correct 1084 ms 48776 KB Output is correct
3 Correct 1159 ms 48772 KB Output is correct
4 Runtime error 60 ms 31232 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16164 KB Output is correct
2 Correct 2041 ms 56068 KB Output is correct
3 Correct 2111 ms 55972 KB Output is correct
4 Correct 595 ms 49356 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16164 KB Output is correct
2 Correct 2041 ms 56068 KB Output is correct
3 Correct 2111 ms 55972 KB Output is correct
4 Correct 595 ms 49356 KB Output is correct
5 Runtime error 58 ms 30692 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16104 KB Output is correct
2 Correct 670 ms 41540 KB Output is correct
3 Correct 1581 ms 46180 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16104 KB Output is correct
2 Correct 670 ms 41540 KB Output is correct
3 Correct 1581 ms 46180 KB Output is correct
4 Incorrect 38 ms 16208 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 44 ms 16196 KB Output is correct
2 Correct 1949 ms 56048 KB Output is correct
3 Correct 2096 ms 55968 KB Output is correct
4 Correct 606 ms 49380 KB Output is correct
5 Correct 39 ms 16080 KB Output is correct
6 Correct 808 ms 41344 KB Output is correct
7 Correct 1687 ms 46048 KB Output is correct
8 Correct 1798 ms 39124 KB Output is correct
9 Correct 1914 ms 45040 KB Output is correct
10 Correct 1624 ms 50844 KB Output is correct
11 Correct 1613 ms 45612 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16196 KB Output is correct
2 Correct 1949 ms 56048 KB Output is correct
3 Correct 2096 ms 55968 KB Output is correct
4 Correct 606 ms 49380 KB Output is correct
5 Correct 39 ms 16080 KB Output is correct
6 Correct 808 ms 41344 KB Output is correct
7 Correct 1687 ms 46048 KB Output is correct
8 Correct 1798 ms 39124 KB Output is correct
9 Correct 1914 ms 45040 KB Output is correct
10 Correct 1624 ms 50844 KB Output is correct
11 Correct 1613 ms 45612 KB Output is correct
12 Runtime error 52 ms 30652 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16000 KB Output is correct
2 Correct 61 ms 17340 KB Output is correct
3 Correct 67 ms 19284 KB Output is correct
4 Correct 77 ms 17616 KB Output is correct
5 Correct 64 ms 17632 KB Output is correct
6 Correct 69 ms 17848 KB Output is correct
7 Correct 40 ms 16308 KB Output is correct
8 Correct 1069 ms 48728 KB Output is correct
9 Correct 1090 ms 48684 KB Output is correct
10 Correct 44 ms 16204 KB Output is correct
11 Correct 2109 ms 56068 KB Output is correct
12 Correct 2023 ms 56056 KB Output is correct
13 Correct 613 ms 49328 KB Output is correct
14 Correct 36 ms 16056 KB Output is correct
15 Correct 668 ms 41372 KB Output is correct
16 Correct 1538 ms 46048 KB Output is correct
17 Correct 1825 ms 39144 KB Output is correct
18 Correct 1881 ms 44996 KB Output is correct
19 Correct 1662 ms 50852 KB Output is correct
20 Correct 1480 ms 45680 KB Output is correct
21 Correct 1068 ms 42800 KB Output is correct
22 Correct 1305 ms 43708 KB Output is correct
23 Correct 2080 ms 42712 KB Output is correct
24 Correct 1934 ms 42760 KB Output is correct
25 Correct 1861 ms 50520 KB Output is correct
26 Correct 1519 ms 45016 KB Output is correct
27 Correct 1532 ms 44612 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16000 KB Output is correct
2 Correct 61 ms 17340 KB Output is correct
3 Correct 67 ms 19284 KB Output is correct
4 Correct 77 ms 17616 KB Output is correct
5 Correct 64 ms 17632 KB Output is correct
6 Correct 69 ms 17848 KB Output is correct
7 Correct 40 ms 16308 KB Output is correct
8 Correct 1069 ms 48728 KB Output is correct
9 Correct 1090 ms 48684 KB Output is correct
10 Correct 44 ms 16204 KB Output is correct
11 Correct 2109 ms 56068 KB Output is correct
12 Correct 2023 ms 56056 KB Output is correct
13 Correct 613 ms 49328 KB Output is correct
14 Correct 36 ms 16056 KB Output is correct
15 Correct 668 ms 41372 KB Output is correct
16 Correct 1538 ms 46048 KB Output is correct
17 Correct 1825 ms 39144 KB Output is correct
18 Correct 1881 ms 44996 KB Output is correct
19 Correct 1662 ms 50852 KB Output is correct
20 Correct 1480 ms 45680 KB Output is correct
21 Correct 1068 ms 42800 KB Output is correct
22 Correct 1305 ms 43708 KB Output is correct
23 Correct 2080 ms 42712 KB Output is correct
24 Correct 1934 ms 42760 KB Output is correct
25 Correct 1861 ms 50520 KB Output is correct
26 Correct 1519 ms 45016 KB Output is correct
27 Correct 1532 ms 44612 KB Output is correct
28 Incorrect 44 ms 16232 KB Extra information in the output file
29 Halted 0 ms 0 KB -