oj.uz

Submission #802050

# Submission time Handle Problem Language Result Execution time Memory
802050 2023-08-02T09:23:50 Z mrwang Regions (IOI09_regions) C++14
65 / 100
 3717 ms 71344 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;
    for(int v:g[u])
    {
        h[v]=h[u]+(k[v]==c);
        dfs(v,c,i);
        cnt[u]+=cnt[v];
    }
    dem1[i][k[u]]+=cnt[u];
    if(k[u]==c) dem1[i][k[u]]--;
    dem2[i][k[u]]+=h[u];
    if(k[u]==c) dem2[i][k[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 7 ms 8528 KB Output is correct
5 Correct 10 ms 8528 KB Output is correct
6 Correct 17 ms 8656 KB Output is correct
7 Correct 28 ms 8656 KB Output is correct
8 Correct 36 ms 8656 KB Output is correct
9 Correct 44 ms 9040 KB Output is correct
10 Correct 87 ms 9296 KB Output is correct
11 Correct 108 ms 9680 KB Output is correct
12 Correct 123 ms 10192 KB Output is correct
13 Correct 166 ms 10192 KB Output is correct
14 Correct 261 ms 11516 KB Output is correct
15 Correct 236 ms 15568 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1101 ms 16792 KB Output isn't correct
2 Incorrect 1090 ms 15468 KB Output isn't correct
3 Correct 1818 ms 19608 KB Output is correct
4 Correct 198 ms 10996 KB Output is correct
5 Correct 306 ms 12140 KB Output is correct
6 Incorrect 545 ms 20740 KB Output isn't correct
7 Correct 755 ms 23684 KB Output is correct
8 Incorrect 918 ms 39880 KB Output isn't correct
9 Correct 2021 ms 21400 KB Output is correct
10 Incorrect 2208 ms 71344 KB Output isn't correct
11 Correct 3717 ms 22660 KB Output is correct
12 Incorrect 1020 ms 27124 KB Output isn't correct
13 Incorrect 1674 ms 27744 KB Output isn't correct
14 Correct 2009 ms 34392 KB Output is correct
15 Correct 2422 ms 33984 KB Output is correct
16 Correct 2534 ms 42656 KB Output is correct
17 Correct 2481 ms 47924 KB Output is correct