oj.uz

Submission #67437

# Submission time Handle Problem Language Result Execution time Memory
67437 2018-08-14T09:26:33 Z Crown Regions (IOI09_regions) C++14
100 / 100
 4465 ms 57696 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;
		int s1 = regions[r1].size(), s2 = regions[r2].size();
		if(s1>= lim || s2>= lim)
		{
			if(s1> s2)
			{
				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 x1 = upper_bound(regions[r2].begin(), regions[r2].end(), rb)-regions[r2].begin();
					int x2 = upper_bound(regions[r2].begin(), regions[r2].end(), lb-1)-regions[r2].begin();
					int cnt2 = x1-x2;
					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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19064 KB Output is correct
2 Correct 19 ms 19252 KB Output is correct
3 Correct 20 ms 19296 KB Output is correct
4 Correct 21 ms 19296 KB Output is correct
5 Correct 22 ms 19312 KB Output is correct
6 Correct 39 ms 19432 KB Output is correct
7 Correct 50 ms 19588 KB Output is correct
8 Correct 50 ms 19644 KB Output is correct
9 Correct 82 ms 20280 KB Output is correct
10 Correct 80 ms 20608 KB Output is correct
11 Correct 177 ms 21016 KB Output is correct
12 Correct 164 ms 21820 KB Output is correct
13 Correct 195 ms 21932 KB Output is correct
14 Correct 273 ms 22772 KB Output is correct
15 Correct 363 ms 25712 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1369 ms 27456 KB Output is correct
2 Correct 1301 ms 27456 KB Output is correct
3 Correct 1671 ms 32124 KB Output is correct
4 Correct 242 ms 32124 KB Output is correct
5 Correct 519 ms 32124 KB Output is correct
6 Correct 640 ms 32124 KB Output is correct
7 Correct 834 ms 32124 KB Output is correct
8 Correct 1378 ms 35676 KB Output is correct
9 Correct 1928 ms 42032 KB Output is correct
10 Correct 4465 ms 49316 KB Output is correct
11 Correct 3192 ms 49316 KB Output is correct
12 Correct 1476 ms 49316 KB Output is correct
13 Correct 1924 ms 49316 KB Output is correct
14 Correct 2754 ms 49316 KB Output is correct
15 Correct 2801 ms 51296 KB Output is correct
16 Correct 2948 ms 57696 KB Output is correct
17 Correct 2879 ms 57696 KB Output is correct