oj.uz

Submission #540393

# Submission time Handle Problem Language Result Execution time Memory
540393 2022-03-20T09:35:25 Z elazarkoren Inside information (BOI21_servers) C++17
2.5 / 100
 3500 ms 12788 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 << 0 << '\n';
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6312 KB Output is correct
2 Correct 35 ms 6888 KB Output is correct
3 Correct 230 ms 6968 KB Output is correct
4 Correct 31 ms 6936 KB Output is correct
5 Correct 32 ms 6788 KB Output is correct
6 Correct 1012 ms 7028 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6312 KB Output is correct
2 Correct 35 ms 6888 KB Output is correct
3 Correct 230 ms 6968 KB Output is correct
4 Correct 31 ms 6936 KB Output is correct
5 Correct 32 ms 6788 KB Output is correct
6 Correct 1012 ms 7028 KB Output is correct
7 Incorrect 22 ms 6220 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6304 KB Output is correct
2 Execution timed out 3563 ms 8348 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 6156 KB Output is correct
2 Correct 83 ms 12524 KB Output is correct
3 Correct 79 ms 12540 KB Output is correct
4 Execution timed out 3578 ms 9992 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 6156 KB Output is correct
2 Correct 83 ms 12524 KB Output is correct
3 Correct 79 ms 12540 KB Output is correct
4 Execution timed out 3578 ms 9992 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6332 KB Output is correct
2 Execution timed out 3563 ms 12788 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 6228 KB Output is correct
2 Correct 79 ms 12416 KB Output is correct
3 Correct 111 ms 12464 KB Output is correct
4 Execution timed out 3592 ms 9876 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 6228 KB Output is correct
2 Correct 79 ms 12416 KB Output is correct
3 Correct 111 ms 12464 KB Output is correct
4 Execution timed out 3592 ms 9876 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6196 KB Output is correct
2 Correct 36 ms 6832 KB Output is correct
3 Correct 248 ms 7272 KB Output is correct
4 Correct 30 ms 6912 KB Output is correct
5 Correct 31 ms 6860 KB Output is correct
6 Correct 987 ms 6952 KB Output is correct
7 Correct 28 ms 6220 KB Output is correct
8 Execution timed out 3554 ms 8864 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6196 KB Output is correct
2 Correct 36 ms 6832 KB Output is correct
3 Correct 248 ms 7272 KB Output is correct
4 Correct 30 ms 6912 KB Output is correct
5 Correct 31 ms 6860 KB Output is correct
6 Correct 987 ms 6952 KB Output is correct
7 Correct 28 ms 6220 KB Output is correct
8 Execution timed out 3554 ms 8864 KB Time limit exceeded
9 Halted 0 ms 0 KB -