oj.uz

Submission #540394

# Submission time Handle Problem Language Result Execution time Memory
540394 2022-03-20T09:36:54 Z elazarkoren Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 9916 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5352 KB Output is correct
2 Correct 34 ms 5400 KB Output is correct
3 Correct 229 ms 5512 KB Output is correct
4 Correct 31 ms 5440 KB Output is correct
5 Correct 31 ms 5424 KB Output is correct
6 Correct 1010 ms 5644 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5352 KB Output is correct
2 Correct 34 ms 5400 KB Output is correct
3 Correct 229 ms 5512 KB Output is correct
4 Correct 31 ms 5440 KB Output is correct
5 Correct 31 ms 5424 KB Output is correct
6 Correct 1010 ms 5644 KB Output is correct
7 Correct 23 ms 5332 KB Output is correct
8 Correct 34 ms 6476 KB Output is correct
9 Correct 403 ms 6656 KB Output is correct
10 Correct 33 ms 6492 KB Output is correct
11 Correct 34 ms 6436 KB Output is correct
12 Correct 1373 ms 6896 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5372 KB Output is correct
2 Execution timed out 3563 ms 7252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5372 KB Output is correct
2 Execution timed out 3563 ms 7252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5300 KB Output is correct
2 Correct 86 ms 9140 KB Output is correct
3 Correct 84 ms 9196 KB Output is correct
4 Execution timed out 3572 ms 8192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5300 KB Output is correct
2 Correct 86 ms 9140 KB Output is correct
3 Correct 84 ms 9196 KB Output is correct
4 Execution timed out 3572 ms 8192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5380 KB Output is correct
2 Execution timed out 3586 ms 9916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5380 KB Output is correct
2 Execution timed out 3586 ms 9916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5484 KB Output is correct
2 Correct 79 ms 9092 KB Output is correct
3 Correct 89 ms 9196 KB Output is correct
4 Execution timed out 3597 ms 8176 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5484 KB Output is correct
2 Correct 79 ms 9092 KB Output is correct
3 Correct 89 ms 9196 KB Output is correct
4 Execution timed out 3597 ms 8176 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5332 KB Output is correct
2 Correct 35 ms 5496 KB Output is correct
3 Correct 238 ms 5552 KB Output is correct
4 Correct 30 ms 5452 KB Output is correct
5 Correct 35 ms 5448 KB Output is correct
6 Correct 978 ms 5488 KB Output is correct
7 Correct 27 ms 5332 KB Output is correct
8 Execution timed out 3568 ms 7320 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5332 KB Output is correct
2 Correct 35 ms 5496 KB Output is correct
3 Correct 238 ms 5552 KB Output is correct
4 Correct 30 ms 5452 KB Output is correct
5 Correct 35 ms 5448 KB Output is correct
6 Correct 978 ms 5488 KB Output is correct
7 Correct 27 ms 5332 KB Output is correct
8 Execution timed out 3568 ms 7320 KB Time limit exceeded
9 Halted 0 ms 0 KB -