oj.uz

Submission #802046

# Submission time Handle Problem Language Result Execution time Memory
802046 2023-08-02T09:21:22 Z mrwang Regions (IOI09_regions) C++14
65 / 100
 3655 ms 71340 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[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]);

            }
            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 7 ms 8524 KB Output is correct
4 Correct 9 ms 8528 KB Output is correct
5 Correct 9 ms 8528 KB Output is correct
6 Correct 17 ms 8700 KB Output is correct
7 Correct 23 ms 8656 KB Output is correct
8 Correct 27 ms 8692 KB Output is correct
9 Correct 42 ms 9040 KB Output is correct
10 Correct 101 ms 9308 KB Output is correct
11 Correct 130 ms 9680 KB Output is correct
12 Correct 134 ms 10192 KB Output is correct
13 Correct 152 ms 10192 KB Output is correct
14 Correct 266 ms 11512 KB Output is correct
15 Correct 231 ms 15628 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1049 ms 16800 KB Output isn't correct
2 Incorrect 1113 ms 15476 KB Output isn't correct
3 Correct 2401 ms 19612 KB Output is correct
4 Correct 256 ms 11004 KB Output is correct
5 Correct 365 ms 12112 KB Output is correct
6 Incorrect 516 ms 20680 KB Output isn't correct
7 Correct 851 ms 23728 KB Output is correct
8 Incorrect 1000 ms 39840 KB Output isn't correct
9 Correct 2390 ms 21404 KB Output is correct
10 Incorrect 2226 ms 71340 KB Output isn't correct
11 Correct 3655 ms 22660 KB Output is correct
12 Incorrect 1188 ms 26972 KB Output isn't correct
13 Incorrect 1540 ms 27740 KB Output isn't correct
14 Correct 1751 ms 34292 KB Output is correct
15 Correct 3098 ms 33984 KB Output is correct
16 Correct 2656 ms 42656 KB Output is correct
17 Correct 2545 ms 47916 KB Output is correct