oj.uz

Submission #53501

# Submission time Handle Problem Language Result Execution time Memory
53501 2018-06-30T06:31:32 Z 장홍준(#2017) Regions (IOI09_regions) C++11
100 / 100
 6359 ms 93180 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define MAX 1000000

int pr[MAX];
int where[MAX];
int childs[MAX];
int childe[MAX];
int transw[MAX];

//FILE *input=freopen("input.txt","r",stdin);

bool sort_transw(int a, int b) {
	if (transw[a]<transw[b])
		return 1;
	return 0;
}
struct xy {
	int x, y;
};

bool sort_x(xy a, xy b) {
	if (a.x<b.x)
		return 1;
	if (a.x>b.x)
		return 0;
	if (a.y>b.y)
		return 1;
	return 0;
}

vector<xy>regions_g[MAX];

vector<int>edge[MAX];
vector<int>regions[MAX];
int cnt;

void dfs(int w) {
	int i;
	childs[w] = cnt;
	childe[w] = cnt;
	transw[w] = cnt;
	cnt++;
	for (i = 0; i<edge[w].size(); i++) {
		dfs(edge[w][i]);
		childe[w] = cnt - 1;
	}
}

int search_left(int w, int k) {
	int s, e;
	int mid;
	s = 0;
	e = regions[w].size() - 1;
	while (1) {
		if (s>e)
			break;
		mid = (s + e) / 2;
		if (k<transw[regions[w][mid]])
			e = mid - 1;
		else if (k>transw[regions[w][mid]])
			s = mid + 1;
		else
			return mid;
	}
	return s;
}
int search_right(int w, int k) {
	int s, e;
	int mid;
	s = 0;
	e = regions[w].size() - 1;
	while (1) {
		if (s>e)
			break;
		mid = (s + e) / 2;
		if (k<transw[regions[w][mid]])
			e = mid - 1;
		else if (k>transw[regions[w][mid]])
			s = mid + 1;
		else
			return mid;
	}
	return e;
}

int main() {
	int i, j;
	int n, r, q;
	int s, e;
	int left;
	int right;
	int sum2, k;
	xy inp;

	int sum = 0;

	scanf(" %d%d%d", &n, &r, &q);
	scanf(" %d", &where[1]);
	regions[where[1]].push_back(1);
	for (i = 2; i <= n; i++) {
		scanf(" %d%d", &pr[i], &where[i]);
		regions[where[i]].push_back(i);
	}
	for (i = 2; i <= n; i++) {
		edge[pr[i]].push_back(i);
	}
	cnt = 1;
	dfs(1);

	for (i = 1; i <= r; i++) {
		sort(regions[i].begin(), regions[i].end(), sort_transw);
	}
	for (i = 1; i <= r; i++) {
		for (j = 0; j<regions[i].size(); j++) {
			inp.x = childs[regions[i][j]];
			inp.y = 1;
			regions_g[i].push_back(inp);
			inp.x = childe[regions[i][j]];
			inp.y = -1;
			regions_g[i].push_back(inp);
		}
		inp.x = 100000;
		inp.y = 0;
		regions_g[i].push_back(inp);
		sort(regions_g[i].begin(), regions_g[i].end(), sort_x);
	}

	for (j = 0; j<q; j++) {
		scanf("%d%d", &s, &e);
		sum = 0;
		sum2 = 0;
		k = 0;
		for (i = 0; i<regions_g[s].size(); i++) {
			if (k >= regions[e].size())
				break;
			while (transw[regions[e][k]]<regions_g[s][i].x || (transw[regions[e][k]] == regions_g[s][i].x&&regions_g[s][i].y == -1)) {
				sum += sum2;
				k++;
				if (k >= regions[e].size())
					break;
			}
			sum2 += regions_g[s][i].y;
		}
		printf("%d\n", sum);
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i<edge[w].size(); i++) {
              ~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j<regions[i].size(); j++) {
               ~^~~~~~~~~~~~~~~~~~
regions.cpp:138:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i<regions_g[s].size(); i++) {
               ~^~~~~~~~~~~~~~~~~~~~
regions.cpp:139:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (k >= regions[e].size())
        ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:144:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (k >= regions[e].size())
         ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:95:6: warning: unused variable 'left' [-Wunused-variable]
  int left;
      ^~~~
regions.cpp:96:6: warning: unused variable 'right' [-Wunused-variable]
  int right;
      ^~~~~
regions.cpp:102: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:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d", &where[1]);
  ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d%d", &pr[i], &where[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 70776 KB Output is correct
2 Correct 62 ms 70864 KB Output is correct
3 Correct 64 ms 70864 KB Output is correct
4 Correct 65 ms 70864 KB Output is correct
5 Correct 66 ms 70864 KB Output is correct
6 Correct 88 ms 70960 KB Output is correct
7 Correct 88 ms 71044 KB Output is correct
8 Correct 98 ms 71044 KB Output is correct
9 Correct 117 ms 71556 KB Output is correct
10 Correct 140 ms 71700 KB Output is correct
11 Correct 172 ms 72092 KB Output is correct
12 Correct 134 ms 72748 KB Output is correct
13 Correct 157 ms 72780 KB Output is correct
14 Correct 252 ms 73504 KB Output is correct
15 Correct 263 ms 75468 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3745 ms 77096 KB Output is correct
2 Correct 6359 ms 77096 KB Output is correct
3 Correct 6345 ms 78696 KB Output is correct
4 Correct 216 ms 78696 KB Output is correct
5 Correct 405 ms 78696 KB Output is correct
6 Correct 700 ms 78696 KB Output is correct
7 Correct 1213 ms 78696 KB Output is correct
8 Correct 1020 ms 81056 KB Output is correct
9 Correct 1839 ms 84172 KB Output is correct
10 Correct 2926 ms 87880 KB Output is correct
11 Correct 2618 ms 87880 KB Output is correct
12 Correct 3116 ms 87880 KB Output is correct
13 Correct 3504 ms 87880 KB Output is correct
14 Correct 4591 ms 87880 KB Output is correct
15 Correct 5017 ms 89924 KB Output is correct
16 Correct 5292 ms 93180 KB Output is correct
17 Correct 5330 ms 93180 KB Output is correct