oj.uz

Submission #67418

# Submission time Handle Problem Language Result Execution time Memory
67418 2018-08-14T08:55:57 Z Crown Regions (IOI09_regions) C++14
27 / 100
 7485 ms 57528 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 21 ms 19108 KB Output is correct
2 Correct 19 ms 19260 KB Output is correct
3 Correct 22 ms 19332 KB Output is correct
4 Correct 22 ms 19380 KB Output is correct
5 Correct 27 ms 19380 KB Output is correct
6 Correct 32 ms 19464 KB Output is correct
7 Correct 48 ms 19488 KB Output is correct
8 Correct 76 ms 19832 KB Output is correct
9 Correct 50 ms 20336 KB Output is correct
10 Incorrect 132 ms 20576 KB Output isn't correct
11 Correct 190 ms 21056 KB Output is correct
12 Incorrect 240 ms 21868 KB Output isn't correct
13 Incorrect 272 ms 21980 KB Output isn't correct
14 Correct 289 ms 22656 KB Output is correct
15 Correct 333 ms 25804 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1204 ms 27592 KB Output is correct
2 Correct 1091 ms 27592 KB Output is correct
3 Correct 1920 ms 32132 KB Output is correct
4 Incorrect 331 ms 32132 KB Output isn't correct
5 Incorrect 481 ms 32132 KB Output isn't correct
6 Incorrect 644 ms 32132 KB Output isn't correct
7 Incorrect 1178 ms 32132 KB Output isn't correct
8 Incorrect 2007 ms 35652 KB Output isn't correct
9 Incorrect 3411 ms 42096 KB Output isn't correct
10 Incorrect 5887 ms 49580 KB Output isn't correct
11 Execution timed out 6533 ms 49580 KB Time limit exceeded (wall clock)
12 Incorrect 6497 ms 49580 KB Unexpected end of file - int32 expected
13 Execution timed out 7314 ms 49580 KB Time limit exceeded (wall clock)
14 Execution timed out 7485 ms 49580 KB Time limit exceeded (wall clock)
15 Incorrect 6405 ms 51232 KB Unexpected end of file - int32 expected
16 Execution timed out 6937 ms 57528 KB Time limit exceeded (wall clock)
17 Execution timed out 7378 ms 57528 KB Time limit exceeded (wall clock)