oj.uz

Submission #1071837

# Submission time Handle Problem Language Result Execution time Memory
1071837 2024-08-23T11:45:06 Z ArthuroWich Regions (IOI09_regions) C++17
45 / 100
 8000 ms 29816 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
vector<int> adj[300005], reg[25005];
int st[300005], en[300005], timer = 0;
void dfs(int i, int p) {
    st[i] = timer;
    timer++;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfs(j, i);
    }
    en[i] = timer;
}
void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        int s, h;
        if (i == 1) {
            cin >> h;
            reg[h].push_back(i);
        } else {
            cin >> s >> h;
            reg[h].push_back(i);
            adj[s].push_back(i);
            adj[i].push_back(s);
        }
    }
    dfs(1, -1);
    while(q--) {
        int a, b, ans = 0;
        cin >> a >> b;
        for (int i : reg[a]) {
            for (int j : reg[b]) {
                if (st[i] < st[j] && st[j] < en[i]) {
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10328 KB Output is correct
3 Correct 3 ms 10328 KB Output is correct
4 Correct 5 ms 10324 KB Output is correct
5 Correct 4 ms 10324 KB Output is correct
6 Correct 10 ms 10584 KB Output is correct
7 Correct 17 ms 10584 KB Output is correct
8 Correct 17 ms 10584 KB Output is correct
9 Correct 23 ms 10840 KB Output is correct
10 Correct 53 ms 10840 KB Output is correct
11 Correct 123 ms 11096 KB Output is correct
12 Correct 118 ms 11608 KB Output is correct
13 Correct 236 ms 13912 KB Output is correct
14 Correct 561 ms 14168 KB Output is correct
15 Correct 543 ms 16216 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8052 ms 16472 KB Time limit exceeded
2 Execution timed out 8026 ms 16572 KB Time limit exceeded
3 Execution timed out 8036 ms 18008 KB Time limit exceeded
4 Correct 229 ms 14168 KB Output is correct
5 Correct 321 ms 15448 KB Output is correct
6 Correct 6822 ms 15252 KB Output is correct
7 Correct 3788 ms 16216 KB Output is correct
8 Correct 2239 ms 20056 KB Output is correct
9 Correct 3761 ms 20560 KB Output is correct
10 Execution timed out 8074 ms 24264 KB Time limit exceeded
11 Execution timed out 8042 ms 22608 KB Time limit exceeded
12 Execution timed out 8042 ms 20816 KB Time limit exceeded
13 Execution timed out 8095 ms 21908 KB Time limit exceeded
14 Execution timed out 8048 ms 22136 KB Time limit exceeded
15 Execution timed out 8013 ms 24416 KB Time limit exceeded
16 Execution timed out 8087 ms 29816 KB Time limit exceeded
17 Execution timed out 8051 ms 28896 KB Time limit exceeded