oj.uz

답안 #912719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912719 2024-01-19T18:42:05 Z anarch_y Regions (IOI09_regions) C++17
14 / 100
 8000 ms 27896 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 home[maxn], dp[maxn];
int ans;

void dfs(int s, int p, int r1, int r2){
    dp[s] = 0;
    if(home[s] == r2) dp[s] = 1;
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s, r1, r2);
        dp[s] += dp[u];
    }
    if(home[s] == r1) ans += dp[s];
}

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

    int N, R, Q; cin >> N >> R >> Q;
    int h; cin >> h; home[1] = h;
    for(int i=2; i<=N; i++){
        int p, g; cin >> p >> g;
        adj[i].pb(p); adj[p].pb(i);
        home[i] = g; 
    }

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        ans = 0;
        dfs(1, 0, r1, r2);
        cout << ans << "\n";
        cout.flush();
    }
}

Subtask #1
14.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6472 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 8 ms 6488 KB Output is correct
6 Correct 23 ms 6488 KB Output is correct
7 Correct 56 ms 6488 KB Output is correct
8 Correct 93 ms 6488 KB Output is correct
9 Correct 229 ms 7000 KB Output is correct
10 Correct 1324 ms 6744 KB Output is correct
11 Correct 2888 ms 7000 KB Output is correct
12 Correct 3593 ms 7372 KB Output is correct
13 Correct 6544 ms 7172 KB Output is correct
14 Execution timed out 8045 ms 7512 KB Time limit exceeded
15 Correct 6703 ms 10840 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8079 ms 10120 KB Time limit exceeded
2 Execution timed out 8019 ms 9240 KB Time limit exceeded
3 Execution timed out 8023 ms 12044 KB Time limit exceeded
4 Execution timed out 8074 ms 7512 KB Time limit exceeded
5 Execution timed out 8080 ms 9584 KB Time limit exceeded
6 Execution timed out 8055 ms 8656 KB Time limit exceeded
7 Execution timed out 8058 ms 9200 KB Time limit exceeded
8 Execution timed out 8064 ms 15460 KB Time limit exceeded
9 Execution timed out 8071 ms 12676 KB Time limit exceeded
10 Execution timed out 8010 ms 19176 KB Time limit exceeded
11 Execution timed out 8080 ms 13532 KB Time limit exceeded
12 Execution timed out 8096 ms 13100 KB Time limit exceeded
13 Execution timed out 8067 ms 14152 KB Time limit exceeded
14 Execution timed out 8054 ms 13552 KB Time limit exceeded
15 Execution timed out 8016 ms 18324 KB Time limit exceeded
16 Execution timed out 8023 ms 27896 KB Time limit exceeded
17 Execution timed out 8055 ms 25972 KB Time limit exceeded