oj.uz

답안 #967547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967547 2024-04-22T12:10:25 Z 12345678 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 24640 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, x, q, p, in[nx], out[nx], t, a, b;
vector<int> d[nx], r[nx];

struct fenwick
{
    int d[nx];
    void update(int i, int vl) {while (i<nx) d[i]+=vl, i+=(i&-i);}
    int query(int i)
    {
        int res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

void dfs(int u)
{
    in[u]=++t;
    for (auto v:d[u]) dfs(v);
    out[u]=t;
}

int main()
{
    cin>>n>>x>>q;
    cin>>x;
    r[x].push_back(1);
    for (int i=2; i<=n; i++) cin>>p>>x, d[p].push_back(i), r[x].push_back(i);
    dfs(1);
    while (q--)
    {
        cin>>a>>b;
        for (auto x:r[b]) f.update(in[x], 1);
        int res=0;
        for (auto x:r[a]) res+=f.query(out[x])-f.query(in[x]-1);
        for (auto x:r[b]) f.update(in[x], -1);
        cout<<res<<'\n';
        fflush(stdout);
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 5 ms 10584 KB Output is correct
5 Correct 7 ms 10584 KB Output is correct
6 Correct 12 ms 10584 KB Output is correct
7 Correct 28 ms 10836 KB Output is correct
8 Correct 24 ms 10584 KB Output is correct
9 Correct 31 ms 10840 KB Output is correct
10 Correct 61 ms 11096 KB Output is correct
11 Correct 111 ms 11188 KB Output is correct
12 Correct 114 ms 11640 KB Output is correct
13 Correct 158 ms 11464 KB Output is correct
14 Correct 261 ms 11864 KB Output is correct
15 Correct 306 ms 13560 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8090 ms 14180 KB Time limit exceeded
2 Execution timed out 8007 ms 13240 KB Time limit exceeded
3 Execution timed out 8087 ms 15468 KB Time limit exceeded
4 Correct 283 ms 11936 KB Output is correct
5 Correct 331 ms 12980 KB Output is correct
6 Correct 1262 ms 12856 KB Output is correct
7 Correct 1883 ms 13516 KB Output is correct
8 Correct 1821 ms 16868 KB Output is correct
9 Correct 2932 ms 17708 KB Output is correct
10 Correct 5300 ms 20952 KB Output is correct
11 Correct 5045 ms 17588 KB Output is correct
12 Execution timed out 8026 ms 19208 KB Time limit exceeded
13 Execution timed out 8039 ms 19048 KB Time limit exceeded
14 Execution timed out 8041 ms 18888 KB Time limit exceeded
15 Execution timed out 8073 ms 21760 KB Time limit exceeded
16 Execution timed out 8012 ms 24640 KB Time limit exceeded
17 Execution timed out 8068 ms 24368 KB Time limit exceeded