oj.uz

Submission #138453

# Submission time Handle Problem Language Result Execution time Memory
138453 2019-07-30T02:22:05 Z baluteshih Regions (IOI09_regions) C++14
95 / 100
 5871 ms 131076 KB 
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ET cout << "\n"
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define MEM memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll B=200,MAXN=200005;
ll ans[MAXN/B][25005],reg[MAXN],in[MAXN],out[MAXN],dft,seq[MAXN],pls[MAXN];
ll bln[25005],bcnt;
vector<ll> G[MAXN],pl[25005];

void dfs(ll u)
{
	in[u]=++dft,seq[dft]=u;
	for(ll i:G[u])
		dfs(i);
	out[u]=dft;
}

int main()
{jizz
	ll n,r,q,a,b;
	cin >> n >> r >> q >> reg[1];
	for(int i=2;i<=n;++i)
		cin >> a >> reg[i],G[a].pb(i);
	dfs(1);
	for(int i=1;i<=n;++i)
		pl[reg[seq[i]]].pb(i);
	for(int i=1;i<=r;++i)
		if(pl[i].size()>=B)
		{
			fill(pls+1,pls+n+1,0),bln[i]=bcnt;
			for(ll j:pl[i])
				++pls[in[seq[j]]+1],--pls[out[seq[j]]+1];
			for(int j=1;j<=n;++j)
				pls[j]+=pls[j-1],ans[bcnt][reg[seq[j]]]+=pls[j];
			++bcnt;
		}
	while(q--)
	{
		cin >> a >> b;
		if(pl[a].size()>=B)
			cout << ans[bln[a]][b] << endl;
		else
		{
			ll ans2=0;
			for(ll i:pl[a])
				if(out[seq[i]]==in[seq[i]]) continue;
				else
					ans2+=upper_bound(ALL(pl[b]),out[seq[i]])-upper_bound(ALL(pl[b]),in[seq[i]]);
			cout << ans2 << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5624 KB Output is correct
2 Correct 6 ms 5624 KB Output is correct
3 Correct 8 ms 5624 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Correct 16 ms 5752 KB Output is correct
6 Correct 25 ms 5624 KB Output is correct
7 Correct 34 ms 5756 KB Output is correct
8 Correct 43 ms 5880 KB Output is correct
9 Correct 44 ms 6268 KB Output is correct
10 Correct 101 ms 6392 KB Output is correct
11 Correct 121 ms 6776 KB Output is correct
12 Correct 169 ms 7304 KB Output is correct
13 Correct 177 ms 7276 KB Output is correct
14 Correct 385 ms 7928 KB Output is correct
15 Correct 507 ms 10260 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1848 ms 12720 KB Output is correct
2 Correct 1034 ms 12536 KB Output is correct
3 Correct 1585 ms 15692 KB Output is correct
4 Correct 312 ms 7860 KB Output is correct
5 Correct 475 ms 9208 KB Output is correct
6 Correct 614 ms 13432 KB Output is correct
7 Correct 1366 ms 16248 KB Output is correct
8 Correct 1304 ms 24336 KB Output is correct
9 Correct 3130 ms 30916 KB Output is correct
10 Correct 3560 ms 96128 KB Output is correct
11 Runtime error 1694 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Correct 2935 ms 61180 KB Output is correct
13 Correct 2823 ms 62176 KB Output is correct
14 Correct 3854 ms 26588 KB Output is correct
15 Correct 5871 ms 24684 KB Output is correct
16 Correct 2716 ms 126212 KB Output is correct
17 Correct 4745 ms 32640 KB Output is correct