Submission #967547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967547	2024-04-22T12:10:25 Z	12345678	Regions (IOI09_regions)	C++17	55 / 100	8000 ms	24640 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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