Submission #540394

#	Time	Username	Problem	Language	Result	Execution time	Memory
540394		elazarkoren	Inside information (BOI21_servers)	C++17	5 / 100	3597 ms	9916 KiB

servers

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 2e5;
const int infinity = 1e9;

vii tree[MAX_N];

//char type[MAX_N];
//int a[MAX_N], d[MAX_N];

//pii dp[20][MAX_N];

bool Dfs(int node, int end, int w) {
    if (node == end) return true;
    for (auto [neighbor, d] : tree[node]) {
        if (d >= w) continue;
        if (Dfs(neighbor, end, d)) {
            return true;
        }
    }
    return false;
}

int Dfs(int node, int w) {
    int c = 1;
    for (auto [neighbor, d] : tree[node]) {
        if (d <= w) continue;
        c += Dfs(neighbor, d);
    }
    return c;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n + k - 1; i++) {
        char type;
        cin >> type;
        if (type == 'S') {
            int a, b;
            cin >> a >> b;
            tree[a].push_back({b, i});
            tree[b].push_back({a, i});
        } else if (type == 'Q') {
            int a, d;
            cin >> a >> d;
            cout << (Dfs(a, d, infinity) ? "yes\n" : "no\n");
        } else {
            int d;
            cin >> d;
            cout << Dfs(d, -1) << '\n';
        }
    }
}

• 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