Submission #496711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
496711	2021-12-22T02:25:06 Z	Dan4Life	Regions (IOI09_regions)	C++17	70 / 100	8000 ms	25284 KB

regions

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,r,q,cnt=1, a[maxn], st[maxn], en[maxn], B[maxn];
vector<int> adj[maxn], v[25001];
void dfs(int s, int p = -1)
{
    st[s] = cnt++;
    for(auto u : adj[s])
        if(u!=p) dfs(u,s);
    en[s] = cnt-1;
}

int32_t main()
{
    cin >> n >> r >> q >> a[1];
    for(int i = 2; i <= n; i++)
    {
        int x; cin >> x >> a[i];
        adj[x].push_back(i);
    }
    dfs(1); for(int i = 1; i <= n; i++) B[st[i]]=i;
    for(int i = 1; i <= n; i++) v[a[B[i]]].push_back(st[B[i]]);
    while(q--)
    {
        int a, b, ans = 0; cin >> a >> b;
        for(auto u : v[a]){
            int l = st[B[u]], r = en[B[u]];
            auto itr = upper_bound(v[b].begin(), v[b].end(), r)-v[b].begin();
            auto itr2 = upper_bound(v[b].begin(), v[b].end(), l)-v[b].begin();
            if(itr) itr--, ans+=max((int)(itr-itr2)+1, 0);
        }
        cout << ans << endl;
    }
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5576 KB	Output is correct
2	Correct	3 ms	5576 KB	Output is correct
3	Correct	5 ms	5576 KB	Output is correct
4	Correct	7 ms	5576 KB	Output is correct
5	Correct	8 ms	5576 KB	Output is correct
6	Correct	22 ms	5576 KB	Output is correct
7	Correct	34 ms	5576 KB	Output is correct
8	Correct	31 ms	5704 KB	Output is correct
9	Correct	51 ms	6088 KB	Output is correct
10	Correct	82 ms	6084 KB	Output is correct
11	Correct	140 ms	6344 KB	Output is correct
12	Correct	166 ms	6856 KB	Output is correct
13	Correct	184 ms	6448 KB	Output is correct
14	Correct	259 ms	7012 KB	Output is correct
15	Correct	207 ms	9536 KB	Output is correct

Subtask #2

55.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8064 ms	10048 KB	Time limit exceeded
2	Execution timed out	8042 ms	8896 KB	Time limit exceeded
3	Execution timed out	8023 ms	11840 KB	Time limit exceeded
4	Correct	233 ms	7104 KB	Output is correct
5	Correct	346 ms	8640 KB	Output is correct
6	Correct	1214 ms	8256 KB	Output is correct
7	Correct	1784 ms	9236 KB	Output is correct
8	Correct	1241 ms	14136 KB	Output is correct
9	Correct	1906 ms	14352 KB	Output is correct
10	Correct	4469 ms	19168 KB	Output is correct
11	Correct	4176 ms	14068 KB	Output is correct
12	Correct	4747 ms	15936 KB	Output is correct
13	Correct	5764 ms	15968 KB	Output is correct
14	Correct	7383 ms	15692 KB	Output is correct
15	Execution timed out	8061 ms	19780 KB	Time limit exceeded
16	Execution timed out	8066 ms	25284 KB	Time limit exceeded
17	Execution timed out	8013 ms	24132 KB	Time limit exceeded