oj.uz

Submission #67428

# Submission time Handle Problem Language Result Execution time Memory
67428 2018-08-14T09:15:37 Z Crown Regions (IOI09_regions) C++14
23 / 100
 8000 ms 57304 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;
		}
		if(regions[r1].empty() || regions[r2].empty())
		{
			printf("0\n");
			fflush(stdout);
			cache[ii(r1, r2)] = 0;
		}
		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
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 19064 KB Output isn't correct
2 Incorrect 18 ms 19176 KB Output isn't correct
3 Incorrect 24 ms 19356 KB Output isn't correct
4 Correct 22 ms 19356 KB Output is correct
5 Correct 33 ms 19356 KB Output is correct
6 Incorrect 27 ms 19436 KB Output isn't correct
7 Correct 64 ms 19556 KB Output is correct
8 Correct 39 ms 19680 KB Output is correct
9 Correct 100 ms 20208 KB Output is correct
10 Incorrect 150 ms 20592 KB Output isn't correct
11 Correct 153 ms 21076 KB Output is correct
12 Incorrect 190 ms 21868 KB Output isn't correct
13 Incorrect 214 ms 21868 KB Output isn't correct
14 Correct 225 ms 22588 KB Output is correct
15 Correct 292 ms 25660 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 27380 KB Output is correct
2 Correct 1163 ms 27380 KB Output is correct
3 Correct 1817 ms 32044 KB Output is correct
4 Incorrect 179 ms 32044 KB Output isn't correct
5 Incorrect 221 ms 32044 KB Output isn't correct
6 Incorrect 222 ms 32044 KB Output isn't correct
7 Incorrect 661 ms 32044 KB Output isn't correct
8 Incorrect 1443 ms 35744 KB Output isn't correct
9 Incorrect 2103 ms 42032 KB Output isn't correct
10 Incorrect 4335 ms 49488 KB Output isn't correct
11 Incorrect 4626 ms 49488 KB Output isn't correct
12 Incorrect 5768 ms 49488 KB Output isn't correct
13 Incorrect 6859 ms 49488 KB Output isn't correct
14 Execution timed out 8050 ms 49488 KB Time limit exceeded
15 Incorrect 6633 ms 51360 KB Unexpected end of file - int32 expected
16 Execution timed out 6979 ms 57304 KB Time limit exceeded (wall clock)
17 Incorrect 6946 ms 57304 KB Unexpected end of file - int32 expected