oj.uz

Submission #720302

# Submission time Handle Problem Language Result Execution time Memory
720302 2023-04-07T22:16:03 Z Johann Inside information (BOI21_servers) C++14
5 / 100
 471 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>

void dfs(vvpii & adj, int v, int t, int source, vvb & reachable) {
    reachable[source][v] = true;
    for (pii e : adj[v]) {
        if (e.second < t) dfs(adj, e.first, e.second, source, reachable);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, K;
    cin >> N >> K;
    vvpii adj(N);
    vvb con(N, vb(N, false));
    for (int i = 0; i < N; ++i) con[i][i] = true;
    for (int t = 1; t < N + K; ++t) {
        string command;
        cin >> command;
        if (command == "S") {
            int a, b;
            cin >> a >> b;
            --a; --b;
            adj[a].push_back({b, t});
            adj[b].push_back({a, t});
            dfs(adj, b, t, a, con);
            dfs(adj, a, t, b, con);
        } else if (command == "Q") {
            int a,d;
            cin >> a >> d;
            --a; --d;
            if (con[a][d]) cout << "yes\n";
            else cout << "no\n";
        } else {
            int d;
            cin >> d;
            --d;
            int cnt = 0;
            for (int i = 0; i < N; ++i) if (con[i][d]) ++cnt;
            cout << cnt << "\n";
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1492 KB Output is correct
2 Correct 35 ms 4360 KB Output is correct
3 Correct 59 ms 4452 KB Output is correct
4 Correct 34 ms 4560 KB Output is correct
5 Correct 35 ms 4340 KB Output is correct
6 Correct 92 ms 4416 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1492 KB Output is correct
2 Correct 35 ms 4360 KB Output is correct
3 Correct 59 ms 4452 KB Output is correct
4 Correct 34 ms 4560 KB Output is correct
5 Correct 35 ms 4340 KB Output is correct
6 Correct 92 ms 4416 KB Output is correct
7 Correct 25 ms 1596 KB Output is correct
8 Correct 434 ms 4104 KB Output is correct
9 Correct 426 ms 4368 KB Output is correct
10 Correct 442 ms 4180 KB Output is correct
11 Correct 395 ms 4288 KB Output is correct
12 Correct 471 ms 4384 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1620 KB Output is correct
2 Runtime error 281 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1620 KB Output is correct
2 Runtime error 281 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1452 KB Output is correct
2 Runtime error 200 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1452 KB Output is correct
2 Runtime error 200 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1552 KB Output is correct
2 Runtime error 202 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1552 KB Output is correct
2 Runtime error 202 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1580 KB Output is correct
2 Runtime error 212 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1580 KB Output is correct
2 Runtime error 212 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1540 KB Output is correct
2 Correct 39 ms 4520 KB Output is correct
3 Correct 41 ms 4516 KB Output is correct
4 Correct 36 ms 4428 KB Output is correct
5 Correct 34 ms 4376 KB Output is correct
6 Correct 97 ms 4496 KB Output is correct
7 Correct 24 ms 1484 KB Output is correct
8 Runtime error 205 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1540 KB Output is correct
2 Correct 39 ms 4520 KB Output is correct
3 Correct 41 ms 4516 KB Output is correct
4 Correct 36 ms 4428 KB Output is correct
5 Correct 34 ms 4376 KB Output is correct
6 Correct 97 ms 4496 KB Output is correct
7 Correct 24 ms 1484 KB Output is correct
8 Runtime error 205 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -