oj.uz

Submission #429306

# Submission time Handle Problem Language Result Execution time Memory
429306 2021-06-15T20:24:43 Z keko37 Inside information (BOI21_servers) C++14
50 / 100
 2029 ms 71528 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];
            if (hi[qa[i]] == n + k) sol[i] = 1;
            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 36 ms 15300 KB Output is correct
2 Correct 55 ms 16160 KB Output is correct
3 Correct 78 ms 18136 KB Output is correct
4 Correct 57 ms 16460 KB Output is correct
5 Correct 59 ms 16388 KB Output is correct
6 Correct 59 ms 16696 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15300 KB Output is correct
2 Correct 55 ms 16160 KB Output is correct
3 Correct 78 ms 18136 KB Output is correct
4 Correct 57 ms 16460 KB Output is correct
5 Correct 59 ms 16388 KB Output is correct
6 Correct 59 ms 16696 KB Output is correct
7 Correct 37 ms 15476 KB Output is correct
8 Runtime error 55 ms 32800 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15432 KB Output is correct
2 Correct 1094 ms 46040 KB Output is correct
3 Correct 1114 ms 46116 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15432 KB Output is correct
2 Correct 1094 ms 46040 KB Output is correct
3 Correct 1114 ms 46116 KB Output is correct
4 Runtime error 48 ms 30548 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 15484 KB Output is correct
2 Correct 1974 ms 52868 KB Output is correct
3 Correct 2028 ms 52808 KB Output is correct
4 Correct 603 ms 46252 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15484 KB Output is correct
2 Correct 1974 ms 52868 KB Output is correct
3 Correct 2028 ms 52808 KB Output is correct
4 Correct 603 ms 46252 KB Output is correct
5 Runtime error 56 ms 30020 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 15400 KB Output is correct
2 Correct 659 ms 38320 KB Output is correct
3 Correct 1580 ms 42960 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15400 KB Output is correct
2 Correct 659 ms 38320 KB Output is correct
3 Correct 1580 ms 42960 KB Output is correct
4 Correct 36 ms 15340 KB Output is correct
5 Runtime error 242 ms 71528 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15456 KB Output is correct
2 Correct 2029 ms 52928 KB Output is correct
3 Correct 1999 ms 52872 KB Output is correct
4 Correct 653 ms 46288 KB Output is correct
5 Correct 46 ms 15380 KB Output is correct
6 Correct 678 ms 38076 KB Output is correct
7 Correct 1444 ms 42764 KB Output is correct
8 Correct 1790 ms 35852 KB Output is correct
9 Correct 1779 ms 41852 KB Output is correct
10 Correct 1543 ms 47548 KB Output is correct
11 Correct 1598 ms 42408 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15456 KB Output is correct
2 Correct 2029 ms 52928 KB Output is correct
3 Correct 1999 ms 52872 KB Output is correct
4 Correct 653 ms 46288 KB Output is correct
5 Correct 46 ms 15380 KB Output is correct
6 Correct 678 ms 38076 KB Output is correct
7 Correct 1444 ms 42764 KB Output is correct
8 Correct 1790 ms 35852 KB Output is correct
9 Correct 1779 ms 41852 KB Output is correct
10 Correct 1543 ms 47548 KB Output is correct
11 Correct 1598 ms 42408 KB Output is correct
12 Runtime error 46 ms 29832 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 37 ms 15200 KB Output is correct
2 Correct 58 ms 15964 KB Output is correct
3 Correct 64 ms 17900 KB Output is correct
4 Correct 59 ms 16164 KB Output is correct
5 Correct 60 ms 16212 KB Output is correct
6 Correct 60 ms 16572 KB Output is correct
7 Correct 36 ms 15296 KB Output is correct
8 Correct 1081 ms 45904 KB Output is correct
9 Correct 1087 ms 45944 KB Output is correct
10 Correct 37 ms 15240 KB Output is correct
11 Correct 2013 ms 52788 KB Output is correct
12 Correct 1911 ms 52760 KB Output is correct
13 Correct 665 ms 46224 KB Output is correct
14 Correct 35 ms 15180 KB Output is correct
15 Correct 682 ms 37992 KB Output is correct
16 Correct 1613 ms 42836 KB Output is correct
17 Correct 1767 ms 35884 KB Output is correct
18 Correct 1778 ms 41768 KB Output is correct
19 Correct 1581 ms 47584 KB Output is correct
20 Correct 1499 ms 42364 KB Output is correct
21 Correct 1054 ms 39372 KB Output is correct
22 Correct 1159 ms 40292 KB Output is correct
23 Correct 1935 ms 39436 KB Output is correct
24 Correct 1856 ms 39484 KB Output is correct
25 Correct 1890 ms 47196 KB Output is correct
26 Correct 1442 ms 41572 KB Output is correct
27 Correct 1515 ms 41316 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15200 KB Output is correct
2 Correct 58 ms 15964 KB Output is correct
3 Correct 64 ms 17900 KB Output is correct
4 Correct 59 ms 16164 KB Output is correct
5 Correct 60 ms 16212 KB Output is correct
6 Correct 60 ms 16572 KB Output is correct
7 Correct 36 ms 15296 KB Output is correct
8 Correct 1081 ms 45904 KB Output is correct
9 Correct 1087 ms 45944 KB Output is correct
10 Correct 37 ms 15240 KB Output is correct
11 Correct 2013 ms 52788 KB Output is correct
12 Correct 1911 ms 52760 KB Output is correct
13 Correct 665 ms 46224 KB Output is correct
14 Correct 35 ms 15180 KB Output is correct
15 Correct 682 ms 37992 KB Output is correct
16 Correct 1613 ms 42836 KB Output is correct
17 Correct 1767 ms 35884 KB Output is correct
18 Correct 1778 ms 41768 KB Output is correct
19 Correct 1581 ms 47584 KB Output is correct
20 Correct 1499 ms 42364 KB Output is correct
21 Correct 1054 ms 39372 KB Output is correct
22 Correct 1159 ms 40292 KB Output is correct
23 Correct 1935 ms 39436 KB Output is correct
24 Correct 1856 ms 39484 KB Output is correct
25 Correct 1890 ms 47196 KB Output is correct
26 Correct 1442 ms 41572 KB Output is correct
27 Correct 1515 ms 41316 KB Output is correct
28 Correct 36 ms 15380 KB Output is correct
29 Runtime error 56 ms 32864 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -