oj.uz

Submission #681992

# Submission time Handle Problem Language Result Execution time Memory
681992 2023-01-15T06:38:35 Z LeVanThuc Regions (IOI09_regions) C++17
100 / 100
 4510 ms 35508 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.inp", "r", stdin);
    freopen("output.out","w", stdout);
#else
#endif
}
static const ll N=2e5+10,Block=450;
ll in[N],out[N],Psol[Block+10][N],Prep[N],e[N],n,r,q,cnt,Pcnt;
vector<ll> gr[N],Reg[N],Member[N];
void dfs(ll u)
{
    in[u]=++cnt;
    Member[e[u]].push_back(in[u]);
    for(auto v:gr[u]) dfs(v);;
    out[u]=cnt;
}
void dfs1(ll u,ll head,ll crr)
{
    if(e[u]==head) crr++;
    Psol[Pcnt][e[u]]+=crr;
    for(auto v:gr[u]) dfs1(v,head,crr);
}
int main()
{
//    online();
    cin>>n>>r>>q;
    cin>>e[1];
    Reg[e[1]].push_back(1);
    for(int i=2;i<=n;i++)
    {
        ll v,c;
        cin>>v>>c;
        gr[v].push_back(i);
        e[i]=c;
        Reg[c].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=r;i++)
    {
        if(Reg[i].size()<Block) continue;
        Prep[i]=++Pcnt;
        dfs1(1,i,0);
    }
//    for(int i=1;i<=r;i++)
//    {
//        for(auto v:Member[i]) cout<<v<<' ';
//        cout<<'\n';
//    }
    while(q--)
    {
        ll a,b;
        cin>>a>>b;
        if(Prep[a]) cout<<Psol[Prep[a]][b]<<endl;
        else
        {
            ll res=0;
            for(auto v:Reg[a])
            {
                res+=lower_bound(Member[b].begin(),Member[b].end(),out[v]+1)-Member[b].begin();
                res-=lower_bound(Member[b].begin(),Member[b].end(),in[v]) -Member[b].begin();
            }
            cout<<res<<endl;
        }
    }
}

Compilation message

regions.cpp: In function 'void online()':
regions.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("output.out","w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 10 ms 14356 KB Output is correct
4 Correct 12 ms 14380 KB Output is correct
5 Correct 16 ms 14416 KB Output is correct
6 Correct 31 ms 14416 KB Output is correct
7 Correct 37 ms 14384 KB Output is correct
8 Correct 44 ms 14416 KB Output is correct
9 Correct 56 ms 14800 KB Output is correct
10 Correct 96 ms 14928 KB Output is correct
11 Correct 126 ms 15184 KB Output is correct
12 Correct 173 ms 15656 KB Output is correct
13 Correct 179 ms 15352 KB Output is correct
14 Correct 315 ms 15948 KB Output is correct
15 Correct 262 ms 17892 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 19068 KB Output is correct
2 Correct 2145 ms 17864 KB Output is correct
3 Correct 2694 ms 20808 KB Output is correct
4 Correct 276 ms 15952 KB Output is correct
5 Correct 353 ms 17224 KB Output is correct
6 Correct 586 ms 19340 KB Output is correct
7 Correct 1559 ms 19068 KB Output is correct
8 Correct 1167 ms 27848 KB Output is correct
9 Correct 2879 ms 23540 KB Output is correct
10 Correct 3556 ms 34332 KB Output is correct
11 Correct 4510 ms 23584 KB Output is correct
12 Correct 1520 ms 25188 KB Output is correct
13 Correct 1688 ms 25312 KB Output is correct
14 Correct 2375 ms 27004 KB Output is correct
15 Correct 2966 ms 29708 KB Output is correct
16 Correct 2855 ms 35040 KB Output is correct
17 Correct 2668 ms 35508 KB Output is correct