oj.uz

Submission #782516

# Submission time Handle Problem Language Result Execution time Memory
782516 2023-07-14T03:59:42 Z PoonYaPat Regions (IOI09_regions) C++14
100 / 100
 4344 ms 94280 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mx=250;
int n,r,q,group[200005],pos[25005],in[200005],out[200005],cc;
ll ans[805][25005];
vector<int> adj[200005],g[25005],v[25005];

void dfs1(int x) {
    in[x]=++cc;
    v[group[x]].push_back(in[x]);
    for (auto s : adj[x]) dfs1(s);
    out[x]=cc;
}

void dfs2(int x, int gr, int c) {
    if (group[x]==gr) ++c;
    else ans[pos[gr]][group[x]]+=c;
    for (auto s : adj[x]) dfs2(s,gr,c);
}

int main() {
    cin>>n>>r>>q>>group[1];
    g[group[1]].push_back(1);
    for (int i=2; i<=n; ++i) {
        int a; cin>>a>>group[i];
        g[group[i]].push_back(i);
        adj[a].push_back(i);
    }
    dfs1(1);
    for (int i=1; i<=r; ++i) sort(v[i].begin(),v[i].end());
    int u=0;
    for (int i=1; i<=r; ++i) if (g[i].size()>mx) pos[i]=++u, dfs2(1,i,0);

    while (q--) {
        int a,b; cin>>a>>b;
        if (g[a].size()>mx) cout<<ans[pos[a]][b]<<endl;
        else {
            ll sum=0;
            for (auto s : g[a]) sum+=(upper_bound(v[b].begin(),v[b].end(),out[s])-lower_bound(v[b].begin(),v[b].end(),in[s]));
            cout<<sum<<endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 6 ms 6096 KB Output is correct
5 Correct 7 ms 6224 KB Output is correct
6 Correct 20 ms 6172 KB Output is correct
7 Correct 22 ms 6224 KB Output is correct
8 Correct 23 ms 6224 KB Output is correct
9 Correct 28 ms 6556 KB Output is correct
10 Correct 69 ms 6736 KB Output is correct
11 Correct 102 ms 6968 KB Output is correct
12 Correct 142 ms 7376 KB Output is correct
13 Correct 146 ms 7120 KB Output is correct
14 Correct 218 ms 7712 KB Output is correct
15 Correct 271 ms 9680 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 10924 KB Output is correct
2 Correct 1318 ms 10052 KB Output is correct
3 Correct 2555 ms 12564 KB Output is correct
4 Correct 269 ms 7752 KB Output is correct
5 Correct 284 ms 8968 KB Output is correct
6 Correct 459 ms 12580 KB Output is correct
7 Correct 930 ms 14268 KB Output is correct
8 Correct 1022 ms 23356 KB Output is correct
9 Correct 2036 ms 27848 KB Output is correct
10 Correct 2649 ms 40244 KB Output is correct
11 Correct 4344 ms 94280 KB Output is correct
12 Correct 1310 ms 17232 KB Output is correct
13 Correct 1810 ms 17260 KB Output is correct
14 Correct 1858 ms 20492 KB Output is correct
15 Correct 2817 ms 21744 KB Output is correct
16 Correct 2629 ms 26916 KB Output is correct
17 Correct 2310 ms 29016 KB Output is correct