oj.uz

Submission #524148

# Submission time Handle Problem Language Result Execution time Memory
524148 2022-02-08T17:38:44 Z keertan Regions (IOI09_regions) C++17
80 / 100
 8000 ms 29084 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;
        while(q--)
        {
            ll r1,r2;
            cin>>r1>>r2;
            
                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 2 ms 200 KB Output is correct
4 Correct 5 ms 200 KB Output is correct
5 Correct 8 ms 328 KB Output is correct
6 Correct 15 ms 328 KB Output is correct
7 Correct 28 ms 328 KB Output is correct
8 Correct 32 ms 456 KB Output is correct
9 Correct 38 ms 968 KB Output is correct
10 Correct 68 ms 1228 KB Output is correct
11 Correct 105 ms 1644 KB Output is correct
12 Correct 134 ms 2388 KB Output is correct
13 Correct 165 ms 2376 KB Output is correct
14 Correct 233 ms 3000 KB Output is correct
15 Correct 261 ms 6288 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 7620 KB Time limit exceeded
2 Execution timed out 8031 ms 7236 KB Time limit exceeded
3 Execution timed out 8048 ms 10004 KB Time limit exceeded
4 Correct 258 ms 3200 KB Output is correct
5 Correct 304 ms 5324 KB Output is correct
6 Correct 920 ms 5212 KB Output is correct
7 Correct 1420 ms 6972 KB Output is correct
8 Correct 1066 ms 13168 KB Output is correct
9 Correct 2052 ms 15096 KB Output is correct
10 Correct 3186 ms 20760 KB Output is correct
11 Correct 3732 ms 18308 KB Output is correct
12 Correct 3292 ms 16684 KB Output is correct
13 Correct 3639 ms 17676 KB Output is correct
14 Correct 5178 ms 18080 KB Output is correct
15 Correct 5676 ms 22016 KB Output is correct
16 Correct 6831 ms 29084 KB Output is correct
17 Execution timed out 8012 ms 27572 KB Time limit exceeded