oj.uz

Submission #802060

# Submission time Handle Problem Language Result Execution time Memory
802060 2023-08-02T09:28:03 Z mrwang Regions (IOI09_regions) C++14
75 / 100
 4132 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;
    h[u]+=k[u]==c;
    for(int v:g[u])
    {
        h[v]=h[u];
        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 5 ms 8528 KB Output is correct
3 Correct 5 ms 8528 KB Output is correct
4 Correct 5 ms 8528 KB Output is correct
5 Correct 11 ms 8528 KB Output is correct
6 Correct 11 ms 8604 KB Output is correct
7 Correct 27 ms 8656 KB Output is correct
8 Correct 34 ms 8656 KB Output is correct
9 Correct 53 ms 9040 KB Output is correct
10 Correct 58 ms 9296 KB Output is correct
11 Correct 88 ms 9748 KB Output is correct
12 Correct 110 ms 10308 KB Output is correct
13 Correct 170 ms 10320 KB Output is correct
14 Correct 256 ms 11512 KB Output is correct
15 Correct 259 ms 15620 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1181 ms 16804 KB Output isn't correct
2 Incorrect 1160 ms 15480 KB Output isn't correct
3 Correct 2524 ms 19608 KB Output is correct
4 Correct 231 ms 10996 KB Output is correct
5 Correct 283 ms 12184 KB Output is correct
6 Incorrect 542 ms 20708 KB Output isn't correct
7 Correct 690 ms 23768 KB Output is correct
8 Incorrect 569 ms 39920 KB Output isn't correct
9 Correct 2147 ms 21408 KB Output is correct
10 Incorrect 2519 ms 71340 KB Output isn't correct
11 Correct 4132 ms 22664 KB Output is correct
12 Correct 1414 ms 26964 KB Output is correct
13 Correct 1866 ms 27740 KB Output is correct
14 Correct 2388 ms 34292 KB Output is correct
15 Correct 3080 ms 33952 KB Output is correct
16 Correct 2983 ms 42660 KB Output is correct
17 Correct 2776 ms 47968 KB Output is correct