oj.uz

Submission #321357

# Submission time Handle Problem Language Result Execution time Memory
321357 2020-11-12T07:27:18 Z ronnith Regions (IOI09_regions) C++14
60 / 100
 8000 ms 29100 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5612 KB Output is correct
2 Correct 4 ms 5612 KB Output is correct
3 Correct 6 ms 5740 KB Output is correct
4 Correct 8 ms 5740 KB Output is correct
5 Correct 10 ms 5868 KB Output is correct
6 Correct 24 ms 6636 KB Output is correct
7 Correct 38 ms 6252 KB Output is correct
8 Correct 36 ms 6508 KB Output is correct
9 Correct 63 ms 7416 KB Output is correct
10 Correct 187 ms 7780 KB Output is correct
11 Correct 160 ms 7524 KB Output is correct
12 Correct 290 ms 8676 KB Output is correct
13 Correct 385 ms 8420 KB Output is correct
14 Correct 310 ms 8040 KB Output is correct
15 Correct 261 ms 11108 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 11236 KB Output is correct
2 Correct 1780 ms 11036 KB Output is correct
3 Correct 1526 ms 13280 KB Output is correct
4 Correct 586 ms 8172 KB Output is correct
5 Correct 696 ms 9572 KB Output is correct
6 Correct 2603 ms 9872 KB Output is correct
7 Correct 3776 ms 11360 KB Output is correct
8 Correct 3965 ms 16356 KB Output is correct
9 Correct 7390 ms 18148 KB Output is correct
10 Execution timed out 8054 ms 22604 KB Time limit exceeded
11 Execution timed out 8092 ms 21860 KB Time limit exceeded
12 Execution timed out 8042 ms 19812 KB Time limit exceeded
13 Execution timed out 8083 ms 20836 KB Time limit exceeded
14 Execution timed out 8032 ms 21264 KB Time limit exceeded
15 Execution timed out 8070 ms 23768 KB Time limit exceeded
16 Execution timed out 8042 ms 29100 KB Time limit exceeded
17 Execution timed out 8093 ms 28208 KB Time limit exceeded