oj.uz

Submission #67431

# Submission time Handle Problem Language Result Execution time Memory
67431 2018-08-14T09:19:07 Z Crown Regions (IOI09_regions) C++14
27 / 100
 7736 ms 55508 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

#define lim 316

const int maxn = 2e5+5;
const int maxr = 3e4+5;

vector<int> adj[maxn];
int re[maxn];
int num[maxn];
int cnt[maxn];
int cur = 0;

int n, r, q;

vector<int> regions[maxn];
vector<int> blocks[maxn];
vector< ii > res[maxn];

void dfs(int u, int p)
{
	cur++;
	num[u] = cur;
	cnt[u] = 1;
	for(auto v : adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
		cnt[u] += cnt[v];
	}
}

bool cmp(int a, int b)
{
	if(abs(a) != abs(b)) return abs(a)< abs(b);
	return a< b;
}

map<ii, ll> cache;

int main()
{
	scanf("%d %d %d", &n, &r, &q);
	scanf("%d", re+1);
	for(int i = 2; i<= n; i++)
	{
		int x;
		scanf("%d %d", &x, &re[i]);
		adj[x].pb(i);
	}
	dfs(1, 0);
	for(int i = 1; i<= n; i++)
	{
		regions[re[i]].pb(num[i]);
		blocks[re[i]].pb(num[i]);
		blocks[re[i]].pb(-num[i]-cnt[i]);
	}
	for(int i = 1; i<= r; i++)
	{
		sort(regions[i].begin(), regions[i].end());
		sort(blocks[i].begin(), blocks[i].end(), cmp);
		vector< ii > tmp;
		for(int j = 0; j< (int) blocks[i].size(); j++)
		{
			if(tmp.empty() || abs(blocks[i][j]) != tmp.back().X)
			{
				tmp.pb(ii(abs(blocks[i][j]), blocks[i][j]>0?1:-1));
			}
			else
			{
				tmp.back().Y += (blocks[i][j]>0?1:-1);
			}
		}
		if(!tmp.empty()) res[i].pb(tmp[0]);
		for(int j = 1; j< (int) tmp.size(); j++)
		{
			res[i].pb(ii(tmp[j].X, res[i].back().Y+tmp[j].Y));
		}
	}
	while(q--)
	{
		int r1, r2; scanf("%d %d", &r1, &r2);
		if(cache.find(ii(r1, r2)) != cache.end())
		{
			printf("%lld\n", cache[ii(r1, r2)]);
			fflush(stdout);
			continue;
		}
		if(regions[r1].empty() || regions[r2].empty())
		{
			printf("0\n");
			fflush(stdout);
			cache[ii(r1, r2)] = 0;
			continue;
		}
		ll ret = 0;
		if(r1>= lim || r2>= lim)
		{
			if(r1> r2)
			{
				for(auto x : regions[r2])
				{
					int ind = upper_bound(res[r1].begin(), res[r1].end(), ii(x, 1e9))-res[r1].begin()-1;
					if(ind< 0) continue;
					ret += res[r1][ind].Y;
				}
			}
			else
			{
				for(int i = 1; i< (int) res[r1].size(); i++)
				{
					int lb = res[r1][i-1].X;
					int rb = res[r1][i].X-1;
					int cnt = res[r1][i-1].Y;
					int cnt2 = lower_bound(regions[r2].begin(), regions[r2].end(), rb)-lower_bound(regions[r2].begin(), regions[r2].end(), lb-1);
					ret += 1LL*cnt*cnt2;
				}
			}
		}
		else
		{
			int pt = 0;
			for(auto x : regions[r2])
			{
				while(pt< (int) res[r1].size() && res[r1][pt].X<= x) pt++;
				if(pt) ret += res[r1][pt-1].Y;
			}
		}
		cache[ii(r1, r2)] = ret;
		printf("%lld\n", ret);
		fflush(stdout);
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", re+1);
  ~~~~~^~~~~~~~~~~~
regions.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &re[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:88:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int r1, r2; scanf("%d %d", &r1, &r2);
               ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19064 KB Output is correct
2 Correct 18 ms 19132 KB Output is correct
3 Correct 23 ms 19184 KB Output is correct
4 Correct 27 ms 19268 KB Output is correct
5 Correct 24 ms 19268 KB Output is correct
6 Correct 37 ms 19440 KB Output is correct
7 Correct 49 ms 19696 KB Output is correct
8 Correct 55 ms 19696 KB Output is correct
9 Correct 68 ms 20284 KB Output is correct
10 Incorrect 108 ms 20664 KB Output isn't correct
11 Correct 137 ms 21032 KB Output is correct
12 Incorrect 166 ms 21944 KB Output isn't correct
13 Incorrect 212 ms 21944 KB Output isn't correct
14 Correct 203 ms 22820 KB Output is correct
15 Correct 214 ms 25852 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 968 ms 27500 KB Output is correct
2 Correct 1221 ms 27500 KB Output is correct
3 Correct 1925 ms 32060 KB Output is correct
4 Incorrect 339 ms 32060 KB Output isn't correct
5 Incorrect 542 ms 32060 KB Output isn't correct
6 Incorrect 690 ms 32060 KB Output isn't correct
7 Incorrect 1031 ms 32060 KB Output isn't correct
8 Incorrect 1576 ms 35760 KB Output isn't correct
9 Incorrect 2882 ms 41972 KB Output isn't correct
10 Incorrect 5521 ms 49464 KB Output isn't correct
11 Execution timed out 6592 ms 49464 KB Time limit exceeded (wall clock)
12 Incorrect 6282 ms 49464 KB Output isn't correct
13 Execution timed out 7221 ms 49464 KB Time limit exceeded (wall clock)
14 Execution timed out 7736 ms 49464 KB Time limit exceeded (wall clock)
15 Execution timed out 6571 ms 49964 KB Time limit exceeded (wall clock)
16 Execution timed out 6426 ms 55508 KB Time limit exceeded (wall clock)
17 Execution timed out 6797 ms 55508 KB Time limit exceeded (wall clock)