oj.uz

Submission #67422

# Submission time Handle Problem Language Result Execution time Memory
67422 2018-08-14T08:57:54 Z Crown Regions (IOI09_regions) C++14
27 / 100
 7750 ms 56248 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));
		}
		assert(res[i].empty() || res[i].back().Y == 0);
	}
	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;
		}
		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:89: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 22 ms 19064 KB Output is correct
2 Correct 22 ms 19252 KB Output is correct
3 Correct 19 ms 19252 KB Output is correct
4 Correct 26 ms 19324 KB Output is correct
5 Correct 24 ms 19392 KB Output is correct
6 Correct 29 ms 19556 KB Output is correct
7 Correct 62 ms 19768 KB Output is correct
8 Correct 55 ms 19768 KB Output is correct
9 Correct 90 ms 20280 KB Output is correct
10 Incorrect 112 ms 20568 KB Output isn't correct
11 Correct 102 ms 21084 KB Output is correct
12 Incorrect 121 ms 21856 KB Output isn't correct
13 Incorrect 219 ms 21944 KB Output isn't correct
14 Correct 246 ms 22584 KB Output is correct
15 Correct 335 ms 25768 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 27348 KB Output is correct
2 Correct 1385 ms 27348 KB Output is correct
3 Correct 1993 ms 32260 KB Output is correct
4 Incorrect 480 ms 32260 KB Output isn't correct
5 Incorrect 436 ms 32260 KB Output isn't correct
6 Incorrect 892 ms 32260 KB Output isn't correct
7 Incorrect 1244 ms 32260 KB Output isn't correct
8 Incorrect 1815 ms 35604 KB Output isn't correct
9 Incorrect 3181 ms 42024 KB Output isn't correct
10 Incorrect 5844 ms 49404 KB Output isn't correct
11 Incorrect 6235 ms 49404 KB Output isn't correct
12 Incorrect 7145 ms 49404 KB Output isn't correct
13 Execution timed out 7458 ms 49404 KB Time limit exceeded (wall clock)
14 Execution timed out 7750 ms 49404 KB Time limit exceeded (wall clock)
15 Execution timed out 6974 ms 50972 KB Time limit exceeded (wall clock)
16 Execution timed out 6730 ms 56248 KB Time limit exceeded (wall clock)
17 Execution timed out 6714 ms 56248 KB Time limit exceeded (wall clock)