Submission #1240627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240627		quannnguyen2009	Inside information (BOI21_servers)	C++20	0 / 100	17 ms	14660 KiB

servers

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1.2e5+5, mod = 1e9+7, inf = 1e18;

int n, q;
vector<ii> adj[N];
vector<ii> q1[N];
vector<int> q2[N];
bool del[N], cur[N], inc[N], dcr[N];
int que[N], sz[N], wgt[N], ans[N];
int bit[2*N];

int get(int p) {
    p++;
    int idx = p, ans = 0;
    while (idx>0) {
        ans += bit[idx];
        idx -= (idx&(-idx));
    }
    return ans;
}

void upd(int u, int v) {
    u++;
    int idx = u;
    while (idx<2*N) {
        bit[idx]+=v;
        idx+=(idx&(-idx));
    }
}

void dfs_sz(int u, int p) {
    sz[u] = 1;
    for (auto [v, w]: adj[u]) {
        if (v==p) continue;
        if (del[v]) continue;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

int find_cen(int u, int p, int n) {
    for (auto [v, w]: adj[u]) {
        if (v==p) continue;
        if (del[v]) continue;
        if (sz[v]*2>n) return find_cen(v, u, n);
    }
    return u;
}

bool cmp(ii a, ii b) {
    return a.se>b.se;
}

void dfs_cal(int u, int p) {
    inc[u] = inc[p];
    if (!del[p] && wgt[u]<wgt[p]) inc[u] = 0;
    dcr[u] = dcr[p];
    if (!del[p] && wgt[u]>wgt[p]) dcr[u] = 0;
    for (auto [it, id]: q1[u]) {
        if (cur[it] && inc[it] && dcr[u] && wgt[it]<=id) ans[id] = 1;
    }
    for (int it: q2[u]) {
        if (dcr[u]) ans[it] += get(it);
    }
    for (auto [v, w]: adj[u]) {
        if (v==p) continue;
        if (del[v]) continue;
        wgt[v] = w;
        dfs_cal(v, u);
    }
}

void dfs_upd(int u, int p) {
    if (inc[u]) {
        upd(wgt[u], 1);
        cur[u] = 1;
    }
    for (auto [v, w]: adj[u]) {
        if (v==p) continue;
        if (del[v]) continue;
        dfs_upd(v, u);
    }
}

void dfs_clear(int u, int p) {
    if (inc[u]) {
        upd(wgt[u], -1);
        cur[u] = 0;
    }
    for (auto [v, w]: adj[u]) {
        if (v==p) continue;
        if (del[v]) continue;
        dfs_clear(v, u);
    }
}

void solve(int u) {
    dfs_sz(u, 0);
    u = find_cen(u, 0, sz[u]);
    del[u] = cur[u] = 1;
    inc[u] = dcr[u] = 1;
    wgt[u] = 0;
    upd(0, 1);
    sort(all(adj[u]), cmp);
    for (auto [v, w]: adj[u]) {
        if (del[v]) continue;
        wgt[v] = w;
        dfs_cal(v, u);
        dfs_upd(v, u);
    }
    for (auto [it, id]: q1[u]) {
        if (cur[it] && inc[it] && wgt[it]<=id) ans[id] = 1;
    }
    for (int it: q2[u]) {
        ans[it] += get(it);
    }
    dfs_clear(u, 0);
    for (auto [v, w]: adj[u]) {
        if (del[v]) continue;
        solve(v);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i=1; i<n+q; i++) {
        char typ; cin >> typ;
        if (typ=='S') {
            int u, v; cin >> u >> v;
            adj[u].pb({v, i});
            adj[v].pb({u, i});
        } else if (typ=='Q') {
            int x, y; cin >> x >> y;
            q1[y].pb({x, i});
            que[i] = 1;
        } else {
            int x; cin >> x;
            q2[x].pb(i);
            que[i] = 2;
        }
    }
    solve(1);
    for (int i=1; i<n+q; i++) {
        if (que[i]==1) {
            if (ans[i]) cout << "yes\n";
            else cout << "no\n";
        } else if (que[i]==2) cout << ans[i] << '\n';
    }
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18