Submission #1112564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112564	2024-11-14T10:41:10 Z	FucKanh	Regions (IOI09_regions)	C++14	45 / 100	8000 ms	26184 KB

regions

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

const int maxn = 2e5 + 2;

int tin[maxn], tout[maxn],t;
vector<int> re[maxn],a[maxn];

void dfs(int u) {
    tin[u] = ++t;
    for (int v : a[u]){
        dfs(v);
    }
    tout[u] = t;
}

void solve() {
    int n,r,q; cin >> n >> r >> q;
    int wat; cin >> wat;
    re[wat].push_back(1);
    int block = sqrt(n);
    for (int i = 2; i <= n; i++) {
        int x,y; cin >> x >> y;
        a[x].push_back(i);
        re[y].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= q; i++) {
        int x,y; cin >> x >> y;
        int ans = 0;
        for (int u : re[x]) {
            for (int v : re[y]) {
                ans += tin[u] <= tin[v] && tout[u] >= tout[v];
            }
        }
        cout << ans << endl;
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:25:9: warning: unused variable 'block' [-Wunused-variable]
   25 |     int block = sqrt(n);
      |         ^~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	12880 KB	Output is correct
2	Correct	3 ms	12880 KB	Output is correct
3	Correct	6 ms	12880 KB	Output is correct
4	Correct	9 ms	13048 KB	Output is correct
5	Correct	14 ms	12880 KB	Output is correct
6	Correct	35 ms	12880 KB	Output is correct
7	Correct	49 ms	12880 KB	Output is correct
8	Correct	60 ms	12880 KB	Output is correct
9	Correct	87 ms	13304 KB	Output is correct
10	Correct	153 ms	13136 KB	Output is correct
11	Correct	257 ms	13404 KB	Output is correct
12	Correct	294 ms	13904 KB	Output is correct
13	Correct	411 ms	13648 KB	Output is correct
14	Correct	800 ms	14160 KB	Output is correct
15	Correct	768 ms	15696 KB	Output is correct

Subtask #2

30.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8025 ms	16208 KB	Time limit exceeded
2	Execution timed out	8051 ms	15440 KB	Time limit exceeded
3	Execution timed out	8031 ms	17488 KB	Time limit exceeded
4	Correct	551 ms	14160 KB	Output is correct
5	Correct	753 ms	15184 KB	Output is correct
6	Correct	7707 ms	14928 KB	Output is correct
7	Correct	4935 ms	15696 KB	Output is correct
8	Correct	3564 ms	19024 KB	Output is correct
9	Correct	5426 ms	19784 KB	Output is correct
10	Execution timed out	8068 ms	22588 KB	Time limit exceeded
11	Execution timed out	8067 ms	19528 KB	Time limit exceeded
12	Execution timed out	8044 ms	20904 KB	Time limit exceeded
13	Execution timed out	8069 ms	20724 KB	Time limit exceeded
14	Execution timed out	8077 ms	20552 KB	Time limit exceeded
15	Execution timed out	8038 ms	23104 KB	Time limit exceeded
16	Execution timed out	8025 ms	26184 KB	Time limit exceeded
17	Execution timed out	8009 ms	25688 KB	Time limit exceeded