Submission #367579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367579	2021-02-17T17:09:41 Z	dapig	Regions (IOI09_regions)	Java 11	0 / 100	5333 ms	71328 KB

regions

import java.io.*;
import java.util.*;

class regions {

	public static void main(String[] args) throws IOException {

		regions obj = new regions();

		obj.doStuff();

	}

	int[] vis;
	void tour() {
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.add(0);
		vis = new int[regvals.length];
		int count = 1;
		while (!q.isEmpty()) {
			int next = q.poll();
			if (vis[next] == 0) {
				vis[next] = count;
				newregvals[regvals[next]].add(count);
				q.push(next);
				for (int i : graph[next]) {
					q.push(i);
				}
				count++;
			} else {
				Stack<int[]> target = regions[regvals[next]];
				int[] toAdd = new int[] {vis[next]-1, count-1};
				while (!target.isEmpty()) {
					int[] top = target.peek();
					if (top[1] <= toAdd[1] && top[0] >= toAdd[0])
						target.pop();
					else break;
				}
				target.add(toAdd);
			}
		}
	}
	
	int bs(int r2, int val) {
		ArrayList<Integer> reg = newregvals[r2];
		int l = 0, r = reg.size()-1;
		while (l < r) {
			int m = (l+r)/2;
			if (reg.get(m) <= val) {
				if (reg.get(m+1) > val) return m;
				l = m+1;
			} else r = m;
		}
		return l;
	}

	int employ, regcount, quers;
	int[] regvals; // region values
	ArrayList<Integer>[] graph;
	
	Stack<int[]>[] regions;
	ArrayList<Integer>[] newregvals;
	
	@SuppressWarnings("unchecked")
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		employ = Integer.parseInt(st.nextToken());
		regcount = Integer.parseInt(st.nextToken());
		quers = Integer.parseInt(st.nextToken());
		regvals = new int[employ];
		graph = new ArrayList[employ];
		regions = new Stack[regcount];
		newregvals = new ArrayList[regcount];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < regions.length; i++) {
			regions[i] = new Stack<>();
			newregvals[i] = new ArrayList<>();
		}
		regvals[0] = Integer.parseInt(br.readLine())-1;
		for (int i = 1; i < regvals.length; i++) {
			st = new StringTokenizer(br.readLine());
			graph[Integer.parseInt(st.nextToken())-1].add(i);
			regvals[i] = Integer.parseInt(st.nextToken())-1;
		}
		
		tour();
		for (int i = 0; i < newregvals.length; i++) {
			newregvals[i].add(Integer.MIN_VALUE);
			Collections.sort(newregvals[i]);
		}
		
		for (int i = 0; i < quers; i++) {
			st = new StringTokenizer(br.readLine());
			int r1 = Integer.parseInt(st.nextToken())-1;
			int r2 = Integer.parseInt(st.nextToken())-1;
			int ans = 0;
			for (int[] j : regions[r1]) {
				ans += (bs(r2, j[1]) - bs(r2, j[0]));
			}
			System.out.println(ans);
			System.out.flush();
		}
		
		br.close();

	}

}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	72 ms	8660 KB	Output isn't correct
2	Incorrect	74 ms	8668 KB	Output isn't correct
3	Incorrect	98 ms	8684 KB	Output isn't correct
4	Incorrect	155 ms	8780 KB	Output isn't correct
5	Incorrect	202 ms	9472 KB	Output isn't correct
6	Incorrect	360 ms	12072 KB	Output isn't correct
7	Incorrect	646 ms	19784 KB	Output isn't correct
8	Incorrect	741 ms	20020 KB	Output isn't correct
9	Incorrect	867 ms	15304 KB	Output isn't correct
10	Incorrect	1091 ms	18320 KB	Output isn't correct
11	Incorrect	1275 ms	19336 KB	Output isn't correct
12	Incorrect	1304 ms	19636 KB	Output isn't correct
13	Incorrect	1438 ms	19604 KB	Output isn't correct
14	Incorrect	1574 ms	20560 KB	Output isn't correct
15	Incorrect	1472 ms	24104 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2291 ms	31068 KB	Output isn't correct
2	Incorrect	2714 ms	28032 KB	Output isn't correct
3	Incorrect	3148 ms	34744 KB	Output isn't correct
4	Incorrect	1426 ms	21588 KB	Output isn't correct
5	Incorrect	1725 ms	25316 KB	Output isn't correct
6	Incorrect	2051 ms	27040 KB	Output isn't correct
7	Incorrect	2534 ms	33124 KB	Output isn't correct
8	Incorrect	2506 ms	42260 KB	Output isn't correct
9	Incorrect	3520 ms	51000 KB	Output isn't correct
10	Incorrect	3989 ms	59408 KB	Output isn't correct
11	Incorrect	5333 ms	60352 KB	Output isn't correct
12	Incorrect	3054 ms	60656 KB	Output isn't correct
13	Incorrect	3345 ms	61504 KB	Output isn't correct
14	Incorrect	3945 ms	63408 KB	Output isn't correct
15	Incorrect	4375 ms	71120 KB	Output isn't correct
16	Incorrect	4295 ms	71328 KB	Output isn't correct
17	Incorrect	4229 ms	68000 KB	Output isn't correct