Submission #560262

#	Time	Username	Problem	Language	Result	Execution time	Memory
560262		Ooops_sorry	Inside information (BOI21_servers)	C++14	0 / 100	3532 ms	524288 KiB

servers

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 1.2e5 + 10, INF = 1e9;
vector<pair<int,int>> g[N], need1[N];
vector<int> sz(N), ans(N), val(N), fir(N), need2[N];
vector<bool> used(N), good(N);
vector<int> arr;

void zhfs(int v, int p) {
    sz[v] = 1;
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first]) {
            zhfs(to.first, v);
            sz[v] += sz[to.first];
        }
    }
}

int find_centroid(int v, int p, int n) {
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && sz[to.first] > n / 2) {
            return find_centroid(to.first, v, n);
        }
    }
    return v;
}

void dfs1(int v, int p, int last, int first_val) {
    val[v] = last;
    fir[v] = first_val;
    good[v] = 1;
    arr.pb(v);
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && to.second > last) {
            dfs1(to.first, v, to.second, (last == -INF ? to.second : first_val));
        }
    }
}

void dfs2(int v, int p, int last, int first_val) {
    for (auto to : need1[v]) {
        if (first_val == fir[to.first]) continue;
        if (good[to.first] && val[to.first] < to.second && first_val < fir[to.first]) {
            ans[to.second] = INF;
        }
    }
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && to.second < last) {
            dfs2(to.first, v, to.second, (last == INF ? to.second : first_val));
        }
    }
}

void solve(int v) {
    zhfs(v, -1);
    arr.clear();
    dfs1(v, -1, -INF, INF);
    dfs2(v, -1, INF, -INF);
    for (auto to : arr) {
        good[to] = 0;
    }
    used[v] = 1;
    for (auto to : g[v]) {
        if (!used[to.first]) {
            solve(find_centroid(to.first, v, sz[to.first]));
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n + k - 1; i++) {
        char c;
        cin >> c;
        if (c == 'S') {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb({b, i});
            g[b].pb({a, i});
            ans[i] = -1;
        } else if (c == 'Q') {
            int a, d;
            cin >> a >> d;
            a--, d--;
            need1[d].pb({a, i});
            ans[i] = INF + 1;
        } else {
            int d;
            cin >> d;
            d--;
            need2[d].pb(i);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) good[j] = 0;
        dfs1(i, -1, -INF, INF);
        for (auto to : need1[i]) {
            if (good[to.first] && val[to.first] < to.second) {
                ans[to.second] = INF;
            }
        }
        for (auto to : need2[i]) {
            int res = 0;
            for (int j = 0; j < n; j++) {
                if (good[j] && val[j] < to) {
                    res++;
                }
            }
            ans[to] = res;
        }
    }
    for (int i = 0; i < n + k - 1; i++) {
        if (ans[i] == -1) continue;
        if (ans[i] >= INF) {
            if (ans[i] == INF) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        } else {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5