oj.uz

Submission #537051

# Submission time Handle Problem Language Result Execution time Memory
537051 2022-03-14T10:30:40 Z stefantaga Regions (IOI09_regions) C++14
100 / 100
 3719 ms 53328 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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 19 ms 464 KB Output is correct
9 Correct 41 ms 976 KB Output is correct
10 Correct 59 ms 1232 KB Output is correct
11 Correct 60 ms 1652 KB Output is correct
12 Correct 126 ms 2392 KB Output is correct
13 Correct 189 ms 2492 KB Output is correct
14 Correct 243 ms 2996 KB Output is correct
15 Correct 241 ms 6292 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 7732 KB Output is correct
2 Correct 2023 ms 7508 KB Output is correct
3 Correct 2581 ms 10224 KB Output is correct
4 Correct 215 ms 3200 KB Output is correct
5 Correct 230 ms 5204 KB Output is correct
6 Correct 1347 ms 5220 KB Output is correct
7 Correct 1297 ms 7092 KB Output is correct
8 Correct 1052 ms 13168 KB Output is correct
9 Correct 1964 ms 15028 KB Output is correct
10 Correct 3713 ms 20764 KB Output is correct
11 Correct 3719 ms 18240 KB Output is correct
12 Correct 1174 ms 18864 KB Output is correct
13 Correct 1697 ms 19884 KB Output is correct
14 Correct 2281 ms 42028 KB Output is correct
15 Correct 2759 ms 25580 KB Output is correct
16 Correct 2890 ms 32872 KB Output is correct
17 Correct 3391 ms 53328 KB Output is correct