oj.uz

Submission #321355

# Submission time Handle Problem Language Result Execution time Memory
321355 2020-11-12T07:21:43 Z ronnith Regions (IOI09_regions) C++14
45 / 100
 8000 ms 29156 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];

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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 4 ms 5612 KB Output is correct
3 Correct 6 ms 5612 KB Output is correct
4 Correct 9 ms 5612 KB Output is correct
5 Correct 11 ms 5612 KB Output is correct
6 Correct 23 ms 5740 KB Output is correct
7 Correct 34 ms 5760 KB Output is correct
8 Correct 37 ms 5740 KB Output is correct
9 Correct 61 ms 6252 KB Output is correct
10 Correct 108 ms 6380 KB Output is correct
11 Correct 177 ms 6764 KB Output is correct
12 Correct 186 ms 7276 KB Output is correct
13 Correct 287 ms 7532 KB Output is correct
14 Correct 457 ms 8044 KB Output is correct
15 Correct 481 ms 10476 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8096 ms 11748 KB Time limit exceeded
2 Execution timed out 8037 ms 11876 KB Time limit exceeded
3 Execution timed out 8087 ms 13796 KB Time limit exceeded
4 Correct 401 ms 8044 KB Output is correct
5 Correct 540 ms 9708 KB Output is correct
6 Correct 2430 ms 9964 KB Output is correct
7 Correct 3510 ms 11364 KB Output is correct
8 Correct 3543 ms 16228 KB Output is correct
9 Correct 6604 ms 18148 KB Output is correct
10 Execution timed out 8019 ms 22628 KB Time limit exceeded
11 Execution timed out 8016 ms 21860 KB Time limit exceeded
12 Execution timed out 8019 ms 19812 KB Time limit exceeded
13 Execution timed out 8032 ms 20836 KB Time limit exceeded
14 Execution timed out 8092 ms 21272 KB Time limit exceeded
15 Execution timed out 8074 ms 23772 KB Time limit exceeded
16 Execution timed out 8083 ms 29156 KB Time limit exceeded
17 Execution timed out 8055 ms 28260 KB Time limit exceeded