oj.uz

Submission #718201

# Submission time Handle Problem Language Result Execution time Memory
718201 2023-04-03T15:43:04 Z bLIC Regions (IOI09_regions) C++17
100 / 100
 3704 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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 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 20 ms 336 KB Output is correct
7 Correct 24 ms 336 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 45 ms 976 KB Output is correct
10 Correct 76 ms 1232 KB Output is correct
11 Correct 95 ms 1616 KB Output is correct
12 Correct 140 ms 2400 KB Output is correct
13 Correct 175 ms 2496 KB Output is correct
14 Correct 263 ms 2896 KB Output is correct
15 Correct 272 ms 6300 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1895 ms 7716 KB Output is correct
2 Correct 2023 ms 7468 KB Output is correct
3 Correct 2781 ms 10220 KB Output is correct
4 Correct 284 ms 3152 KB Output is correct
5 Correct 182 ms 5208 KB Output is correct
6 Correct 1370 ms 5212 KB Output is correct
7 Correct 1637 ms 7016 KB Output is correct
8 Correct 1297 ms 13160 KB Output is correct
9 Correct 1799 ms 15084 KB Output is correct
10 Correct 3458 ms 20756 KB Output is correct
11 Correct 3704 ms 18236 KB Output is correct
12 Correct 1503 ms 18864 KB Output is correct
13 Correct 1834 ms 19876 KB Output is correct
14 Correct 2656 ms 42072 KB Output is correct
15 Correct 2777 ms 25580 KB Output is correct
16 Correct 2806 ms 32876 KB Output is correct
17 Correct 2890 ms 53320 KB Output is correct