Submission #321357

#	Time	Username	Problem	Language	Result	Execution time	Memory
321357		ronnith	Regions (IOI09_regions)	C++14	60 / 100	8093 ms	29100 KiB

regions

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i = a;i < b;i ++)
#define trav(e,x) for(auto e:x)
#define maxn 200000
#define maxr 25000

using ll = long long;

using namespace std;

ll N, R, Q, timer, region[maxn], st[maxn], en[maxn];
vector<ll> adj[maxn], nodes[maxr];
ll an[500][500];

struct Bit
{
	ll n;
	vector<ll> bit;
	Bit(int _n)
	{
		n = _n;
		bit.assign(n,0);
	}
	void upd(int i, ll u)
	{
		while(i < n)
		{
			bit[i] += u;
			i += ((i + 1) & (-i - 1));
		}
	}
	ll sum(int i)
	{
		ll res = 0;
		while(i >= 0)
		{
			res += bit[i];
			i -= ((i + 1) & (-i - 1));
		}
		return res;
	}
};

void dfs(ll x,ll pr)
{
	st[x] = timer ++;
	trav(e,adj[x])
	{
		if(e != pr)
		{
			dfs(e,x);
		}
	}
	en[x] = timer - 1;
}

//

void dfs2(ll x,ll pr,ll crr,ll val)
{
	if(region[x] == crr)val ++;
	an[crr][region[x]] += val;
	trav(e,adj[x])
	{
		if(e != pr)
		{
			dfs2(e,x,crr,val);
		}
	}
}

void preProccess()
{
	FOR(i,0,R)
	{
		dfs2(0,-1,i,0);
	}
}

//


int main()
{
	scanf("%lld%lld%lld",&N,&R,&Q);
	
	ll x,y;
	scanf("%lld",&x);
	region[0] = x - 1;
	nodes[x - 1].push_back(0);
	FOR(i,0,N - 1)
	{
		scanf("%lld%lld",&x,&y);
		x --;y --;
		adj[i + 1].push_back(x);
		adj[x].push_back(i + 1);
		region[i + 1] = y;
		nodes[y].push_back(i + 1);
	}

	if(R <= 500)
	{

		preProccess();

		FOR(i,0,Q)
		{
			ll ans = 0;
			scanf("%lld%lld",&x,&y);
			x --;y --;
			printf("%lld\n", an[x][y]);
			fflush(stdout);
		}

		return 0;
	}

	dfs(0,-1);

	Bit bit(N);

	FOR(i,0,Q)
	{
		ll ans = 0;
		scanf("%lld%lld",&x,&y);
		x --;y --;

		trav(e,nodes[x])
		{
			bit.upd(st[e],1);
			bit.upd(en[e] + 1,-1);
		}

		trav(e,nodes[y])
		{
			// cout << "yes";
			ans += bit.sum(st[e]);
		}

		trav(e,nodes[x])
		{
			bit.upd(st[e],-1);
			bit.upd(en[e] + 1,1);
		}

		printf("%lld\n", ans);
		fflush(stdout);
	}

	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:109:7: warning: unused variable 'ans' [-Wunused-variable]
  109 |    ll ans = 0;
      |       ^~~
regions.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%lld%lld%lld",&N,&R,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |  scanf("%lld",&x);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:110:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |    scanf("%lld%lld",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 85