oj.uz

Submission #477250

# Submission time Handle Problem Language Result Execution time Memory
477250 2021-10-01T12:04:44 Z hackerbhaiya Regions (IOI09_regions) C++14
100 / 100
 3947 ms 53316 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
// #define ll long long
#define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (int)1e9
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

const int N=512;
ll n,r,q,tt=1;
vector<vector<ll> > v;
vector<vector<pair<ll,ll> > > reg;
vector<ll> st,en,euler,region;

void dfs(int cur, int par)
{
    st[cur]=tt++,euler.pb(region[cur]);
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i];
        if(node!=par)
            dfs(node,cur);
    }
    en[cur]=tt-1;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        cin>>n>>r>>q;
        v.rz(n+1),st.rz(n+1),en.rz(n+1),reg.rz(r+1),region.rz(n+1);
        cin>>region[1];
        reg[region[1]].pb({1,0});
        f(i,2,n+1)
        {
            ll num;
            cin>>num>>region[i];
            v[i].pb(num),v[num].pb(i),reg[region[i]].pb({i,0});
        }
        euler.pb(0);
        dfs(1,1);
        f(i,1,r+1)
        {
            f(j,0,sz(reg[i]))
                reg[i][j]=mp(st[reg[i][j].ff],en[reg[i][j].ff]);
            sort(all(reg[i]));
        }
        euler.pb(0);
        map<pair<ll,ll>,ll> val;
        f(i,1,r+1)
        {
            if(sz(reg[i])>N)
            {
                vector<ll> tot(tt+2);
                f(j,0,sz(reg[i]))
                    tot[reg[i][j].ff]++,tot[reg[i][j].ss+1]--;
                f(j,1,tt+1)
                {
                    tot[j]+=tot[j-1];
                    val[{i,euler[j]}]+=tot[j];
                }
            }
        }
        while(q--)
        {
            ll r1,r2;
            cin>>r1>>r2;
            if(sz(reg[r1])>N)
                cout<<val[{r1,r2}]<<endl;
            else
            {
                ll ans=0;
                f(i,0,sz(reg[r1]))
                    ans+=(ub(all(reg[r2]),mp(reg[r1][i].ss,inf))-lb(all(reg[r2]),mp(reg[r1][i].ff,-1)));
                cout<<ans<<endl;
            }
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 9 ms 328 KB Output is correct
6 Correct 15 ms 328 KB Output is correct
7 Correct 29 ms 328 KB Output is correct
8 Correct 16 ms 456 KB Output is correct
9 Correct 47 ms 968 KB Output is correct
10 Correct 75 ms 1192 KB Output is correct
11 Correct 108 ms 1608 KB Output is correct
12 Correct 122 ms 2384 KB Output is correct
13 Correct 160 ms 2480 KB Output is correct
14 Correct 277 ms 3016 KB Output is correct
15 Correct 280 ms 6284 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1880 ms 7716 KB Output is correct
2 Correct 1954 ms 7460 KB Output is correct
3 Correct 2786 ms 10220 KB Output is correct
4 Correct 305 ms 3188 KB Output is correct
5 Correct 366 ms 5276 KB Output is correct
6 Correct 1243 ms 5208 KB Output is correct
7 Correct 1427 ms 6972 KB Output is correct
8 Correct 1213 ms 13156 KB Output is correct
9 Correct 2090 ms 15036 KB Output is correct
10 Correct 3654 ms 20760 KB Output is correct
11 Correct 3947 ms 18392 KB Output is correct
12 Correct 1441 ms 18856 KB Output is correct
13 Correct 1891 ms 19868 KB Output is correct
14 Correct 2611 ms 42012 KB Output is correct
15 Correct 3047 ms 25576 KB Output is correct
16 Correct 2969 ms 32864 KB Output is correct
17 Correct 3353 ms 53316 KB Output is correct