Submission #67414

# Submission time Handle Problem Language Result Execution time Memory
67414 2018-08-14T08:49:21 Z Crown Regions (IOI09_regions) C++14
0 / 100
1878 ms 86480 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);
			}
		}
		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)
		{
			assert(0);
			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);
               ~~~~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 38008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 54 ms 38164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 51 ms 38260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 29 ms 38308 KB Unexpected end of file - int32 expected
5 Incorrect 36 ms 38432 KB Unexpected end of file - int32 expected
6 Runtime error 49 ms 38576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 55 ms 38752 KB Unexpected end of file - int32 expected
8 Incorrect 55 ms 38928 KB Unexpected end of file - int32 expected
9 Incorrect 72 ms 39472 KB Unexpected end of file - int32 expected
10 Runtime error 48 ms 40204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 178 ms 41108 KB Expected integer, but "prog1:" found
12 Runtime error 81 ms 42444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 63 ms 42560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 241 ms 43648 KB Expected integer, but "prog1:" found
15 Incorrect 209 ms 46892 KB Expected integer, but "prog1:" found
# Verdict Execution time Memory Grader output
1 Incorrect 953 ms 48720 KB Expected integer, but "prog1:" found
2 Incorrect 1209 ms 48720 KB Expected integer, but "prog1:" found
3 Incorrect 1878 ms 53252 KB Expected integer, but "prog1:" found
4 Runtime error 70 ms 53252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 68 ms 53252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 84 ms 53252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 82 ms 53252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 141 ms 62672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 161 ms 62672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 168 ms 71424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 212 ms 71424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 216 ms 71424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 178 ms 71424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 221 ms 71424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 218 ms 76152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 218 ms 86480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 194 ms 86480 KB Execution killed with signal 11 (could be triggered by violating memory limits)