Submission #321355

#	Time	Username	Problem	Language	Result	Execution time	Memory
321355		ronnith	Regions (IOI09_regions)	C++14	45 / 100	8096 ms	29156 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];

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;
}

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);
	}

	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:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%lld%lld%lld",&N,&R,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%lld",&x);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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