Submission #909105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909105	2024-01-17T05:19:36 Z	anarch_y	Regions (IOI09_regions)	C++17	45 / 100	8000 ms	23672 KB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

const int maxn = 200001;
vector<int> adj[maxn];
int st[maxn], en[maxn];
int timer = 0;

void dfs(int s, int p){
    st[s] = timer++;
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
    }
    en[s] = timer;
}

bool anc(int a, int b){
    return st[a] <= st[b] and en[b] <= en[a];
}

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

    int N, R, Q; cin >> N >> R >> Q;
    vector<int> reg[R+1];
    int h; cin >> h;
    reg[h].pb(1);
    for(int i=2; i<=N; i++){
        int p, r; cin >> p >> r;
        adj[i].pb(p); adj[p].pb(i);
        reg[r].pb(i);
    }
    dfs(1, 0);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        for(auto a: reg[r1]){
            for(auto b: reg[r2]){
                if(anc(a, b)) ans++;
            }
        }
        cout << ans << "\n";
        cout.flush();
    }
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6488 KB	Output is correct
2	Correct	2 ms	6488 KB	Output is correct
3	Correct	5 ms	6488 KB	Output is correct
4	Correct	4 ms	6488 KB	Output is correct
5	Correct	5 ms	6488 KB	Output is correct
6	Correct	10 ms	6488 KB	Output is correct
7	Correct	18 ms	6488 KB	Output is correct
8	Correct	21 ms	6488 KB	Output is correct
9	Correct	31 ms	7000 KB	Output is correct
10	Correct	53 ms	7000 KB	Output is correct
11	Correct	122 ms	7000 KB	Output is correct
12	Correct	133 ms	7668 KB	Output is correct
13	Correct	242 ms	7512 KB	Output is correct
14	Correct	621 ms	7768 KB	Output is correct
15	Correct	576 ms	9856 KB	Output is correct

Subtask #2

30.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8085 ms	10004 KB	Time limit exceeded
2	Execution timed out	8005 ms	9616 KB	Time limit exceeded
3	Execution timed out	8086 ms	11372 KB	Time limit exceeded
4	Correct	189 ms	8024 KB	Output is correct
5	Correct	262 ms	9304 KB	Output is correct
6	Correct	7901 ms	9040 KB	Output is correct
7	Correct	4238 ms	9844 KB	Output is correct
8	Correct	2497 ms	13836 KB	Output is correct
9	Correct	4066 ms	13708 KB	Output is correct
10	Execution timed out	8021 ms	18232 KB	Time limit exceeded
11	Execution timed out	8055 ms	15396 KB	Time limit exceeded
12	Execution timed out	8079 ms	14232 KB	Time limit exceeded
13	Execution timed out	8064 ms	15092 KB	Time limit exceeded
14	Execution timed out	8079 ms	15212 KB	Time limit exceeded
15	Execution timed out	8052 ms	18216 KB	Time limit exceeded
16	Execution timed out	8038 ms	23672 KB	Time limit exceeded
17	Execution timed out	8010 ms	22564 KB	Time limit exceeded