Submission #751415

#	Time	Username	Problem	Language	Result	Execution time	Memory
751415		vjudge1	Inside information (BOI21_servers)	C++17	5 / 100	3552 ms	10748 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 120'000;

/*int par[1 + maxn];
int sz[1 + maxn];

void make_set(int a) {
    par[a] = a;
    sz[a] = 1;
}

int find_set(int a) {
    if(a == par[a]) {
        return a;
    }
    return par[a] = find_set(par[a]);
}

void union_sets(int a, int b) {
    a = find_set(a), b = find_set(b);
    if(sz[a] < sz[b]) {
        swap(a, b);
    }
    sz[b] += sz[a];
    par[a] = b;
}*/

int tree[1 + 4 * maxn];

void update(int v, int vl, int vr, int pos, int val) {
    if(vl == vr) {
        tree[v] = val;
        return;
    }
    int mid = (vl + vr) / 2;
    if(pos <= mid) {
        update(2 * v, vl, mid, pos, val);
    } else {
        update(2 * v + 1, mid + 1, vr, pos, val);
    }
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int query(int v, int vl, int vr, int ql, int qr) {
    if(vl > qr || vr < ql) {
        return 0;
    }
    if(vl == ql && vr == qr) {
        return tree[v];
    }
    int mid = (vl + vr) / 2;
    return query(2 * v, vl, mid, ql, min(qr, mid)) +
        query(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr);
}

int n, q;
vector<pii > graph[1 + maxn];
int target;
bool has;

int dfs(int cur, int par, int last) {
    if(cur == target) {
        has = true;
    }
    int res = 1;
    for(pii nei : graph[cur]) {
        if(nei.fi == par) {
            continue;
        }
        if(nei.se < last) {
            continue;
        }
        res += dfs(nei.fi, cur, nei.se);
    }
    return res;
}

void solve() {
    cin >> n >> q;
    q += n - 1;
    int edge_cnt = 0;
    while(q--) {
        string type;
        cin >> type;
        if(type == "S") {
            int a, b;
            cin >> a >> b;
            edge_cnt++;
            graph[a].pb({b, edge_cnt});
            graph[b].pb({a, edge_cnt});
        }
        if(type == "Q") {
            int a, b;
            cin >> a >> b;
            target = a;
            has = false;
            dfs(b, 0, 0);
            if(has) {
                cout << "yes";
            } else {
                cout << "no";
            }
            cout << "\n";
        }
        if(type == "C") {
            int a;
            cin >> a;
            int cnt = dfs(a, 0, 0);
            cout << cnt << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 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