oj.uz

Submission #67417

# Submission time Handle Problem Language Result Execution time Memory
67417 2018-08-14T08:55:26 Z Crown Regions (IOI09_regions) C++14
0 / 100
 230 ms 45676 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));
		}
	}
	return 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 19064 KB Unexpected end of file - int32 expected
2 Incorrect 19 ms 19256 KB Unexpected end of file - int32 expected
3 Incorrect 18 ms 19256 KB Unexpected end of file - int32 expected
4 Incorrect 18 ms 19256 KB Unexpected end of file - int32 expected
5 Incorrect 20 ms 19284 KB Unexpected end of file - int32 expected
6 Incorrect 19 ms 19412 KB Unexpected end of file - int32 expected
7 Incorrect 21 ms 19412 KB Unexpected end of file - int32 expected
8 Incorrect 21 ms 19488 KB Unexpected end of file - int32 expected
9 Incorrect 23 ms 20000 KB Unexpected end of file - int32 expected
10 Incorrect 25 ms 20156 KB Unexpected end of file - int32 expected
11 Incorrect 30 ms 20540 KB Unexpected end of file - int32 expected
12 Incorrect 32 ms 21180 KB Unexpected end of file - int32 expected
13 Incorrect 42 ms 21180 KB Unexpected end of file - int32 expected
14 Incorrect 42 ms 21948 KB Unexpected end of file - int32 expected
15 Incorrect 54 ms 24764 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 25800 KB Unexpected end of file - int32 expected
2 Incorrect 89 ms 25800 KB Unexpected end of file - int32 expected
3 Incorrect 86 ms 28060 KB Unexpected end of file - int32 expected
4 Incorrect 44 ms 28060 KB Unexpected end of file - int32 expected
5 Incorrect 90 ms 28060 KB Unexpected end of file - int32 expected
6 Incorrect 57 ms 28060 KB Unexpected end of file - int32 expected
7 Incorrect 91 ms 28060 KB Unexpected end of file - int32 expected
8 Incorrect 88 ms 31548 KB Unexpected end of file - int32 expected
9 Incorrect 144 ms 33852 KB Unexpected end of file - int32 expected
10 Incorrect 145 ms 39340 KB Unexpected end of file - int32 expected
11 Incorrect 224 ms 39340 KB Unexpected end of file - int32 expected
12 Incorrect 222 ms 39340 KB Unexpected end of file - int32 expected
13 Incorrect 178 ms 39340 KB Unexpected end of file - int32 expected
14 Incorrect 197 ms 39340 KB Unexpected end of file - int32 expected
15 Incorrect 230 ms 39940 KB Unexpected end of file - int32 expected
16 Incorrect 173 ms 45676 KB Unexpected end of file - int32 expected
17 Incorrect 178 ms 45676 KB Unexpected end of file - int32 expected