답안 #67409 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67409	2018-08-14T08:38:39 Z	Crown	Regions (IOI09_regions)	C++14	0 / 100	2073 ms	86668 KB

regions

#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)
		{
			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
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	39 ms	38008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	40 ms	38092 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	48 ms	38120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Incorrect	25 ms	38176 KB	Unexpected end of file - int32 expected
5	Incorrect	26 ms	38252 KB	Unexpected end of file - int32 expected
6	Runtime error	51 ms	38504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Incorrect	50 ms	38832 KB	Unexpected end of file - int32 expected
8	Incorrect	54 ms	38924 KB	Unexpected end of file - int32 expected
9	Incorrect	112 ms	39564 KB	Unexpected end of file - int32 expected
10	Incorrect	124 ms	39836 KB	Unexpected end of file - int32 expected
11	Incorrect	151 ms	40280 KB	Unexpected end of file - int32 expected
12	Incorrect	160 ms	41172 KB	Unexpected end of file - int32 expected
13	Incorrect	191 ms	41172 KB	Unexpected end of file - int32 expected
14	Incorrect	200 ms	41884 KB	Unexpected end of file - int32 expected
15	Incorrect	255 ms	44880 KB	Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1065 ms	46632 KB	Unexpected end of file - int32 expected
2	Incorrect	1332 ms	46632 KB	Unexpected end of file - int32 expected
3	Incorrect	2073 ms	51460 KB	Unexpected end of file - int32 expected
4	Runtime error	57 ms	51460 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	64 ms	51460 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	86 ms	51460 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	106 ms	51460 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	143 ms	62540 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	136 ms	62540 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	166 ms	71404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	165 ms	71404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	222 ms	71404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	169 ms	71404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	204 ms	71404 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	237 ms	76140 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	200 ms	86668 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	179 ms	86668 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #67409

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 85.0

Subtask #1
0 / 15.0

Subtask #2
0 / 85.0