oj.uz

Submission #802084

# Submission time Handle Problem Language Result Execution time Memory
802084 2023-08-02T09:36:40 Z mrwang Regions (IOI09_regions) C++14
100 / 100
 3445 ms 71368 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll in[maxN],out[maxN],tg=0,h[maxN],cnt[maxN],ct[maxN];
ll dem1[450][25001],dem2[450][25001];
vector<ll>g[maxN];
void DFS(ll u)
{
    in[u]=++tg;
    for(int v:g[u])
    {
        DFS(v);
    }
    out[u]=tg;
}
ll k[maxN];
void dfs(ll u,ll c,ll i)
{
    cnt[u]=k[u]==c;
    h[u]+=k[u]==c;
    if(u==1)
    {
        h[1]=k[u]==c;
    }
    for(int v:g[u])
    {
        h[v]=h[u];
        dfs(v,c,i);
        cnt[u]+=cnt[v];
    }
    dem1[i][k[u]]+=cnt[u];

    dem2[i][k[u]]+=h[u];
}
ll n,r,q;
vector<ll>vv[25001],vec[25001];
ll pp[maxN];
void solve()
{
    cin >> n >> r >> q;
    for(int i=1;i<=n;i++)
    {

        if(i!=1)
        {
            ll p;
            cin >> p;
            g[p].pb(i);
        }
        cin >> k[i];
        ct[k[i]]++;
        vv[k[i]].pb(i);
    }

    ll sz=0;
    DFS(1);
    for(int i=1;i<=r;i++)
    {
        if(ct[i]*ct[i]>n)
        {
            ++sz;
            pp[i]=sz;
            dfs(1,i,sz);
        }
    }
    for(int i=1;i<=n;i++)
    {
        vec[k[i]].pb(in[i]);
    }
    for(int i=1;i<=r;i++) sort(vec[i].begin(),vec[i].end());
    for(int i=1;i<=q;i++)
    {
        ll x,y;
        cin >> x >> y;
        if(ct[x]*ct[x]>n)
        {
            cout << dem2[pp[x]][y]<<endl;
        }
        else if(ct[y]*ct[y]>n)
        {
            cout << dem1[pp[y]][x]<<endl;
        }
        else
        {
            ll ans=0;
            for(auto zz:vv[x])
            {
                ans+=upper_bound(vec[y].begin(),vec[y].end(),out[zz])-lower_bound(vec[y].begin(),vec[y].end(),in[zz]+1);
            }
            cout << ans<<endl;
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8528 KB Output is correct
2 Correct 4 ms 8528 KB Output is correct
3 Correct 6 ms 8528 KB Output is correct
4 Correct 6 ms 8528 KB Output is correct
5 Correct 12 ms 8528 KB Output is correct
6 Correct 20 ms 8656 KB Output is correct
7 Correct 25 ms 8656 KB Output is correct
8 Correct 34 ms 8656 KB Output is correct
9 Correct 49 ms 9040 KB Output is correct
10 Correct 66 ms 9296 KB Output is correct
11 Correct 99 ms 9680 KB Output is correct
12 Correct 102 ms 10232 KB Output is correct
13 Correct 163 ms 10192 KB Output is correct
14 Correct 218 ms 11416 KB Output is correct
15 Correct 230 ms 15620 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 16796 KB Output is correct
2 Correct 845 ms 15480 KB Output is correct
3 Correct 2080 ms 19616 KB Output is correct
4 Correct 280 ms 10988 KB Output is correct
5 Correct 233 ms 12112 KB Output is correct
6 Correct 466 ms 20736 KB Output is correct
7 Correct 650 ms 23876 KB Output is correct
8 Correct 964 ms 39900 KB Output is correct
9 Correct 2023 ms 21396 KB Output is correct
10 Correct 2093 ms 71368 KB Output is correct
11 Correct 3445 ms 22656 KB Output is correct
12 Correct 1236 ms 26972 KB Output is correct
13 Correct 1614 ms 27744 KB Output is correct
14 Correct 1893 ms 34360 KB Output is correct
15 Correct 2700 ms 33952 KB Output is correct
16 Correct 2678 ms 42664 KB Output is correct
17 Correct 2484 ms 47924 KB Output is correct