oj.uz

Submission #802045

# Submission time Handle Problem Language Result Execution time Memory
802045 2023-08-02T09:21:02 Z mrwang Regions (IOI09_regions) C++14
50 / 100
 2613 ms 47912 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];
    dem2[i][k[u]]+=h[u];
}
ll n,r,q;
vector<ll>vv[25000],vec[25000];
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]);

            }
            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 5 ms 8528 KB Output is correct
4 Correct 8 ms 8528 KB Output is correct
5 Correct 10 ms 8528 KB Output is correct
6 Correct 20 ms 8656 KB Output is correct
7 Correct 23 ms 8656 KB Output is correct
8 Correct 35 ms 8656 KB Output is correct
9 Correct 51 ms 9040 KB Output is correct
10 Correct 79 ms 9316 KB Output is correct
11 Correct 117 ms 9680 KB Output is correct
12 Correct 117 ms 10448 KB Output is correct
13 Correct 180 ms 10192 KB Output is correct
14 Correct 234 ms 11508 KB Output is correct
15 Correct 261 ms 15696 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1075 ms 16804 KB Output isn't correct
2 Incorrect 1220 ms 15484 KB Output isn't correct
3 Correct 2199 ms 19612 KB Output is correct
4 Correct 215 ms 10992 KB Output is correct
5 Correct 306 ms 12172 KB Output is correct
6 Incorrect 577 ms 20668 KB Output isn't correct
7 Correct 720 ms 23676 KB Output is correct
8 Incorrect 949 ms 39936 KB Output isn't correct
9 Correct 1732 ms 21400 KB Output is correct
10 Runtime error 16 ms 18756 KB Execution killed with signal 11
11 Runtime error 33 ms 23020 KB Execution killed with signal 11
12 Incorrect 1042 ms 26972 KB Output isn't correct
13 Incorrect 1483 ms 27744 KB Output isn't correct
14 Correct 2191 ms 34332 KB Output is correct
15 Runtime error 34 ms 26684 KB Execution killed with signal 11
16 Runtime error 58 ms 32176 KB Execution killed with signal 11
17 Correct 2613 ms 47912 KB Output is correct