oj.uz

Submission #910110

# Submission time Handle Problem Language Result Execution time Memory
910110 2024-01-17T22:37:44 Z MinaRagy06 Inside information (BOI21_servers) C++17
5 / 100
 1010 ms 2644 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

const int N = 4005;
vector<array<int, 2>> adj[N];

bool dfs(int i, int prvt, int par, int tar) {
    if (i == tar) return 1;
    bool ok = 0;
    for (auto [nxt, t] : adj[i]) {
        if (nxt == par) continue;
        if (prvt > t) {
            ok |= dfs(nxt, t, i, tar);
        }
    }
    return ok;
}
int dfs2(int i, int prvt, int par) {
    int ans = 1;
    for (auto [nxt, t] : adj[i]) {
        if (nxt == par) continue;
        if (prvt < t) {
            ans += dfs2(nxt, t, i);
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    q += n - 1;
    for (int cur = 0; cur < q; cur++) {
        char t;
        int a, b;
        cin >> t >> a;
        if (t == 'S') {
            cin >> b;
            adj[a].push_back({b, cur});
            adj[b].push_back({a, cur});
        } else if (t == 'Q') {
            cin >> b;
            cout << (dfs(a, 1e9, -1, b)? "yes\n" : "no\n");
        } else {
            cout << dfs2(a, -1e9, -1) << '\n';
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Correct 25 ms 848 KB Output is correct
3 Correct 175 ms 1104 KB Output is correct
4 Correct 23 ms 860 KB Output is correct
5 Correct 23 ms 860 KB Output is correct
6 Correct 926 ms 1308 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Correct 25 ms 848 KB Output is correct
3 Correct 175 ms 1104 KB Output is correct
4 Correct 23 ms 860 KB Output is correct
5 Correct 23 ms 860 KB Output is correct
6 Correct 926 ms 1308 KB Output is correct
7 Correct 17 ms 860 KB Output is correct
8 Correct 24 ms 856 KB Output is correct
9 Correct 243 ms 1104 KB Output is correct
10 Correct 23 ms 2392 KB Output is correct
11 Correct 24 ms 1884 KB Output is correct
12 Correct 921 ms 2644 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 860 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 860 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 860 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 860 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 740 KB Output is correct
2 Correct 27 ms 860 KB Output is correct
3 Correct 182 ms 1100 KB Output is correct
4 Correct 24 ms 908 KB Output is correct
5 Correct 27 ms 944 KB Output is correct
6 Correct 1010 ms 948 KB Output is correct
7 Correct 22 ms 860 KB Output is correct
8 Runtime error 2 ms 760 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 740 KB Output is correct
2 Correct 27 ms 860 KB Output is correct
3 Correct 182 ms 1100 KB Output is correct
4 Correct 24 ms 908 KB Output is correct
5 Correct 27 ms 944 KB Output is correct
6 Correct 1010 ms 948 KB Output is correct
7 Correct 22 ms 860 KB Output is correct
8 Runtime error 2 ms 760 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -