Submission #138454

#	Time	Username	Problem	Language	Result	Execution time	Memory
138454		baluteshih	Regions (IOI09_regions)	C++14	100 / 100	5156 ms	97064 KiB

regions

#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 / 15
• Subtask 2: 85 / 85