oj.uz

Submission #802036

# Submission time Handle Problem Language Result Execution time Memory
802036 2023-08-02T09:16:49 Z mrwang Regions (IOI09_regions) C++14
50 / 100
 2403 ms 45556 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=2e5+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][25000],dem2[450][25000];
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 6224 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 5 ms 6224 KB Output is correct
4 Correct 7 ms 6224 KB Output is correct
5 Correct 9 ms 6224 KB Output is correct
6 Correct 20 ms 6224 KB Output is correct
7 Correct 29 ms 6352 KB Output is correct
8 Correct 31 ms 6352 KB Output is correct
9 Correct 37 ms 6736 KB Output is correct
10 Correct 77 ms 6964 KB Output is correct
11 Correct 107 ms 7376 KB Output is correct
12 Correct 129 ms 7888 KB Output is correct
13 Correct 159 ms 7852 KB Output is correct
14 Correct 238 ms 9168 KB Output is correct
15 Correct 235 ms 13264 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 976 ms 14452 KB Output isn't correct
2 Incorrect 1193 ms 13116 KB Output isn't correct
3 Correct 2025 ms 17256 KB Output is correct
4 Correct 164 ms 8652 KB Output is correct
5 Correct 333 ms 9788 KB Output is correct
6 Incorrect 389 ms 18332 KB Output isn't correct
7 Correct 849 ms 21352 KB Output is correct
8 Incorrect 712 ms 37476 KB Output isn't correct
9 Correct 2050 ms 19048 KB Output is correct
10 Runtime error 15 ms 14044 KB Execution killed with signal 11
11 Runtime error 26 ms 18216 KB Execution killed with signal 11
12 Incorrect 1101 ms 24624 KB Output isn't correct
13 Incorrect 1548 ms 25380 KB Output isn't correct
14 Correct 1973 ms 31932 KB Output is correct
15 Runtime error 30 ms 21848 KB Execution killed with signal 11
16 Runtime error 54 ms 27436 KB Execution killed with signal 11
17 Correct 2403 ms 45556 KB Output is correct