oj.uz

답안 #1112564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112564 2024-11-14T10:41:10 Z FucKanh Regions (IOI09_regions) C++14
45 / 100
 8000 ms 26184 KB 
#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

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

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