oj.uz

Submission #138454

# Submission time Handle Problem Language Result Execution time Memory
138454 2019-07-30T02:25:13 Z baluteshih Regions (IOI09_regions) C++14
100 / 100
 5156 ms 97064 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 int B=250,MAXN=200005;
ll ans[MAXN/B][25005],pls[MAXN];
int reg[MAXN],in[MAXN],out[MAXN],dft,seq[MAXN],bln[25005],bcnt;
vector<int> G[MAXN],pl[25005];

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

int main()
{jizz
	int 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(int 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(int 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 9 ms 5624 KB Output is correct
4 Correct 12 ms 5624 KB Output is correct
5 Correct 16 ms 5752 KB Output is correct
6 Correct 16 ms 5624 KB Output is correct
7 Correct 35 ms 5752 KB Output is correct
8 Correct 44 ms 5752 KB Output is correct
9 Correct 58 ms 6008 KB Output is correct
10 Correct 99 ms 6136 KB Output is correct
11 Correct 147 ms 6452 KB Output is correct
12 Correct 176 ms 6904 KB Output is correct
13 Correct 206 ms 6652 KB Output is correct
14 Correct 363 ms 7148 KB Output is correct
15 Correct 442 ms 8952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2260 ms 10668 KB Output is correct
2 Correct 1651 ms 10128 KB Output is correct
3 Correct 4096 ms 12208 KB Output is correct
4 Correct 334 ms 7160 KB Output is correct
5 Correct 455 ms 8436 KB Output is correct
6 Correct 654 ms 12280 KB Output is correct
7 Correct 1498 ms 13944 KB Output is correct
8 Correct 1130 ms 22264 KB Output is correct
9 Correct 2457 ms 27576 KB Output is correct
10 Correct 4311 ms 38776 KB Output is correct
11 Correct 5105 ms 97064 KB Output is correct
12 Correct 2318 ms 17660 KB Output is correct
13 Correct 3223 ms 17528 KB Output is correct
14 Correct 3445 ms 20812 KB Output is correct
15 Correct 5156 ms 20868 KB Output is correct
16 Correct 5066 ms 30928 KB Output is correct
17 Correct 4618 ms 26928 KB Output is correct