oj.uz

Submission #67429

# Submission time Handle Problem Language Result Execution time Memory
67429 2018-08-14T09:17:07 Z Crown Regions (IOI09_regions) C++14
27 / 100
 7983 ms 57400 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;
		}
		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 22 ms 19064 KB Output is correct
2 Correct 22 ms 19252 KB Output is correct
3 Correct 24 ms 19312 KB Output is correct
4 Correct 25 ms 19360 KB Output is correct
5 Correct 26 ms 19428 KB Output is correct
6 Correct 52 ms 19568 KB Output is correct
7 Correct 30 ms 19568 KB Output is correct
8 Correct 68 ms 19716 KB Output is correct
9 Correct 91 ms 20316 KB Output is correct
10 Incorrect 119 ms 20528 KB Output isn't correct
11 Correct 205 ms 21040 KB Output is correct
12 Incorrect 126 ms 21856 KB Output isn't correct
13 Incorrect 266 ms 21856 KB Output isn't correct
14 Correct 213 ms 22692 KB Output is correct
15 Correct 262 ms 25748 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 27284 KB Output is correct
2 Correct 1006 ms 27284 KB Output is correct
3 Correct 1894 ms 31992 KB Output is correct
4 Incorrect 392 ms 31992 KB Output isn't correct
5 Incorrect 385 ms 31992 KB Output isn't correct
6 Incorrect 759 ms 31992 KB Output isn't correct
7 Incorrect 909 ms 31992 KB Output isn't correct
8 Incorrect 1670 ms 35764 KB Output isn't correct
9 Incorrect 3177 ms 42064 KB Output isn't correct
10 Incorrect 5378 ms 49428 KB Output isn't correct
11 Incorrect 5820 ms 49428 KB Output isn't correct
12 Incorrect 6019 ms 49428 KB Output isn't correct
13 Execution timed out 7983 ms 49428 KB Time limit exceeded (wall clock)
14 Execution timed out 7859 ms 49428 KB Time limit exceeded (wall clock)
15 Execution timed out 6807 ms 50216 KB Time limit exceeded (wall clock)
16 Execution timed out 6739 ms 57400 KB Time limit exceeded (wall clock)
17 Execution timed out 6929 ms 57400 KB Time limit exceeded (wall clock)