Submission #429299

#	Time	Username	Problem	Language	Result	Execution time	Memory
429299		keko37	Inside information (BOI21_servers)	C++14	50 / 100	2111 ms	56068 KiB

servers

#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 (stderr)

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5