Submission #367591

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367591	2021-02-17T17:44:54 Z	dapig	Regions (IOI09_regions)	Java 11	0 / 100	5083 ms	71212 KB

regions

//package eulertour;

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	81 ms	8556 KB	Output isn't correct
2	Incorrect	77 ms	8640 KB	Output isn't correct
3	Incorrect	97 ms	8704 KB	Output isn't correct
4	Incorrect	147 ms	8848 KB	Output isn't correct
5	Incorrect	192 ms	9452 KB	Output isn't correct
6	Incorrect	356 ms	11944 KB	Output isn't correct
7	Incorrect	664 ms	19908 KB	Output isn't correct
8	Incorrect	714 ms	20260 KB	Output isn't correct
9	Incorrect	903 ms	15336 KB	Output isn't correct
10	Incorrect	1031 ms	18420 KB	Output isn't correct
11	Incorrect	1227 ms	19296 KB	Output isn't correct
12	Incorrect	1305 ms	19752 KB	Output isn't correct
13	Incorrect	1342 ms	19756 KB	Output isn't correct
14	Incorrect	1459 ms	20832 KB	Output isn't correct
15	Incorrect	1500 ms	24044 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2271 ms	31016 KB	Output isn't correct
2	Incorrect	2577 ms	28076 KB	Output isn't correct
3	Incorrect	3181 ms	34828 KB	Output isn't correct
4	Incorrect	1472 ms	21832 KB	Output isn't correct
5	Incorrect	1649 ms	25416 KB	Output isn't correct
6	Incorrect	2080 ms	27224 KB	Output isn't correct
7	Incorrect	2593 ms	33136 KB	Output isn't correct
8	Incorrect	2424 ms	42052 KB	Output isn't correct
9	Incorrect	3274 ms	51148 KB	Output isn't correct
10	Incorrect	3738 ms	59252 KB	Output isn't correct
11	Incorrect	5083 ms	60456 KB	Output isn't correct
12	Incorrect	2868 ms	60728 KB	Output isn't correct
13	Incorrect	3169 ms	61688 KB	Output isn't correct
14	Incorrect	3872 ms	63472 KB	Output isn't correct
15	Incorrect	4158 ms	71212 KB	Output isn't correct
16	Incorrect	4238 ms	71196 KB	Output isn't correct
17	Incorrect	4373 ms	67968 KB	Output isn't correct