oj.uz

Submission #67432

# Submission time Handle Problem Language Result Execution time Memory
67432 2018-08-14T09:20:06 Z Crown Regions (IOI09_regions) C++14
30 / 100
 4988 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 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19064 KB Output is correct
2 Correct 19 ms 19128 KB Output is correct
3 Correct 21 ms 19128 KB Output is correct
4 Correct 24 ms 19180 KB Output is correct
5 Correct 32 ms 19236 KB Output is correct
6 Correct 45 ms 19480 KB Output is correct
7 Correct 63 ms 19568 KB Output is correct
8 Correct 84 ms 19600 KB Output is correct
9 Correct 90 ms 20268 KB Output is correct
10 Correct 72 ms 20608 KB Output is correct
11 Correct 165 ms 21128 KB Output is correct
12 Correct 191 ms 21932 KB Output is correct
13 Correct 180 ms 21940 KB Output is correct
14 Correct 173 ms 22644 KB Output is correct
15 Correct 280 ms 25772 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1274 ms 27356 KB Output isn't correct
2 Incorrect 1338 ms 27356 KB Output isn't correct
3 Incorrect 1827 ms 32064 KB Output isn't correct
4 Correct 348 ms 32064 KB Output is correct
5 Correct 473 ms 32064 KB Output is correct
6 Incorrect 904 ms 32064 KB Output isn't correct
7 Incorrect 897 ms 32064 KB Output isn't correct
8 Incorrect 1787 ms 35588 KB Output isn't correct
9 Incorrect 1734 ms 42040 KB Output isn't correct
10 Incorrect 4988 ms 49464 KB Output isn't correct
11 Correct 3338 ms 49464 KB Output is correct
12 Incorrect 1422 ms 49464 KB Output isn't correct
13 Incorrect 2210 ms 49464 KB Output isn't correct
14 Incorrect 3128 ms 49464 KB Output isn't correct
15 Incorrect 3035 ms 51352 KB Output isn't correct
16 Incorrect 3546 ms 57696 KB Output isn't correct
17 Incorrect 3561 ms 57696 KB Output isn't correct