oj.uz

Submission #802040

# Submission time Handle Problem Language Result Execution time Memory
802040 2023-08-02T09:19:08 Z mrwang Regions (IOI09_regions) C++14
50 / 100
 2437 ms 47904 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][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 5 ms 8528 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 5 ms 8528 KB Output is correct
4 Correct 8 ms 8528 KB Output is correct
5 Correct 11 ms 8528 KB Output is correct
6 Correct 15 ms 8784 KB Output is correct
7 Correct 17 ms 8656 KB Output is correct
8 Correct 26 ms 8656 KB Output is correct
9 Correct 34 ms 9040 KB Output is correct
10 Correct 81 ms 9296 KB Output is correct
11 Correct 88 ms 9680 KB Output is correct
12 Correct 134 ms 10304 KB Output is correct
13 Correct 146 ms 10192 KB Output is correct
14 Correct 253 ms 11536 KB Output is correct
15 Correct 255 ms 15624 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 835 ms 16784 KB Output isn't correct
2 Incorrect 1141 ms 15476 KB Output isn't correct
3 Correct 2039 ms 19620 KB Output is correct
4 Correct 251 ms 10996 KB Output is correct
5 Correct 258 ms 12104 KB Output is correct
6 Incorrect 568 ms 20780 KB Output isn't correct
7 Correct 783 ms 23724 KB Output is correct
8 Incorrect 831 ms 39960 KB Output isn't correct
9 Correct 2132 ms 21404 KB Output is correct
10 Runtime error 20 ms 18812 KB Execution killed with signal 11
11 Runtime error 27 ms 22976 KB Execution killed with signal 11
12 Incorrect 1040 ms 26976 KB Output isn't correct
13 Incorrect 1635 ms 27744 KB Output isn't correct
14 Correct 1823 ms 34284 KB Output is correct
15 Runtime error 40 ms 26652 KB Execution killed with signal 11
16 Runtime error 57 ms 32112 KB Execution killed with signal 11
17 Correct 2437 ms 47904 KB Output is correct