oj.uz

Submission #523984

# Submission time Handle Problem Language Result Execution time Memory
523984 2022-02-08T14:03:52 Z keertan Regions (IOI09_regions) C++17
100 / 100
 3500 ms 53320 KB 
#include<bits/stdc++.h>
#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 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 8 ms 328 KB Output is correct
6 Correct 18 ms 328 KB Output is correct
7 Correct 23 ms 456 KB Output is correct
8 Correct 31 ms 456 KB Output is correct
9 Correct 36 ms 968 KB Output is correct
10 Correct 80 ms 1224 KB Output is correct
11 Correct 111 ms 1656 KB Output is correct
12 Correct 134 ms 2392 KB Output is correct
13 Correct 152 ms 2376 KB Output is correct
14 Correct 255 ms 2984 KB Output is correct
15 Correct 263 ms 6296 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1758 ms 7724 KB Output is correct
2 Correct 2033 ms 7472 KB Output is correct
3 Correct 2459 ms 10220 KB Output is correct
4 Correct 218 ms 3208 KB Output is correct
5 Correct 326 ms 5196 KB Output is correct
6 Correct 1202 ms 5216 KB Output is correct
7 Correct 1541 ms 7080 KB Output is correct
8 Correct 1263 ms 13156 KB Output is correct
9 Correct 2045 ms 15040 KB Output is correct
10 Correct 3252 ms 20768 KB Output is correct
11 Correct 3500 ms 18324 KB Output is correct
12 Correct 1284 ms 18856 KB Output is correct
13 Correct 1588 ms 19872 KB Output is correct
14 Correct 2692 ms 42016 KB Output is correct
15 Correct 3216 ms 25572 KB Output is correct
16 Correct 2797 ms 32856 KB Output is correct
17 Correct 3467 ms 53320 KB Output is correct