oj.uz

답안 #751415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751415 2023-05-31T14:26:16 Z vjudge1 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 10748 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 4328 KB Output is correct
2 Correct 54 ms 4904 KB Output is correct
3 Correct 129 ms 4992 KB Output is correct
4 Correct 49 ms 5004 KB Output is correct
5 Correct 50 ms 4916 KB Output is correct
6 Correct 1238 ms 5036 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 4328 KB Output is correct
2 Correct 54 ms 4904 KB Output is correct
3 Correct 129 ms 4992 KB Output is correct
4 Correct 49 ms 5004 KB Output is correct
5 Correct 50 ms 4916 KB Output is correct
6 Correct 1238 ms 5036 KB Output is correct
7 Correct 39 ms 4260 KB Output is correct
8 Correct 43 ms 4684 KB Output is correct
9 Correct 188 ms 4808 KB Output is correct
10 Correct 42 ms 4680 KB Output is correct
11 Correct 48 ms 4656 KB Output is correct
12 Correct 1161 ms 4932 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 4308 KB Output is correct
2 Execution timed out 3547 ms 6408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 4308 KB Output is correct
2 Execution timed out 3547 ms 6408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 4288 KB Output is correct
2 Correct 126 ms 10536 KB Output is correct
3 Correct 119 ms 10600 KB Output is correct
4 Execution timed out 3509 ms 8940 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 4288 KB Output is correct
2 Correct 126 ms 10536 KB Output is correct
3 Correct 119 ms 10600 KB Output is correct
4 Execution timed out 3509 ms 8940 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4344 KB Output is correct
2 Execution timed out 3531 ms 10748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4344 KB Output is correct
2 Execution timed out 3531 ms 10748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 4368 KB Output is correct
2 Correct 142 ms 10632 KB Output is correct
3 Correct 110 ms 10652 KB Output is correct
4 Execution timed out 3521 ms 9136 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 4368 KB Output is correct
2 Correct 142 ms 10632 KB Output is correct
3 Correct 110 ms 10652 KB Output is correct
4 Execution timed out 3521 ms 9136 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4296 KB Output is correct
2 Correct 45 ms 5012 KB Output is correct
3 Correct 104 ms 5088 KB Output is correct
4 Correct 41 ms 4940 KB Output is correct
5 Correct 49 ms 4976 KB Output is correct
6 Correct 1116 ms 5252 KB Output is correct
7 Correct 42 ms 4300 KB Output is correct
8 Execution timed out 3552 ms 6192 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4296 KB Output is correct
2 Correct 45 ms 5012 KB Output is correct
3 Correct 104 ms 5088 KB Output is correct
4 Correct 41 ms 4940 KB Output is correct
5 Correct 49 ms 4976 KB Output is correct
6 Correct 1116 ms 5252 KB Output is correct
7 Correct 42 ms 4300 KB Output is correct
8 Execution timed out 3552 ms 6192 KB Time limit exceeded
9 Halted 0 ms 0 KB -