oj.uz

답안 #909105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
909105 2024-01-17T05:19:36 Z anarch_y Regions (IOI09_regions) C++17
45 / 100
 8000 ms 23672 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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