Submission #367602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367602	2021-02-17T18:10:38 Z	dapig	Regions (IOI09_regions)	Java 11	45 / 100	8000 ms	70288 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 {
				ArrayList<int[]> target = regions[regvals[next]];
				int[] toAdd = new int[] {vis[next]-1, count-1};
				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;
	
	ArrayList<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 ArrayList[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 ArrayList<>();
			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);
		}
		
		br.close();

	}

}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	8412 KB	Output is correct
2	Correct	76 ms	8528 KB	Output is correct
3	Correct	105 ms	8556 KB	Output is correct
4	Correct	151 ms	8816 KB	Output is correct
5	Correct	194 ms	9344 KB	Output is correct
6	Correct	376 ms	11800 KB	Output is correct
7	Correct	515 ms	14612 KB	Output is correct
8	Correct	686 ms	19300 KB	Output is correct
9	Correct	856 ms	16808 KB	Output is correct
10	Correct	1010 ms	17648 KB	Output is correct
11	Correct	1241 ms	18740 KB	Output is correct
12	Correct	1237 ms	19728 KB	Output is correct
13	Correct	1318 ms	19168 KB	Output is correct
14	Correct	1437 ms	20768 KB	Output is correct
15	Correct	1529 ms	24944 KB	Output is correct

Subtask #2

30.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8045 ms	31588 KB	Time limit exceeded
2	Execution timed out	8031 ms	29784 KB	Time limit exceeded
3	Execution timed out	8039 ms	35652 KB	Time limit exceeded
4	Correct	1553 ms	21176 KB	Output is correct
5	Correct	1682 ms	25564 KB	Output is correct
6	Correct	3371 ms	27380 KB	Output is correct
7	Correct	3928 ms	33284 KB	Output is correct
8	Correct	3651 ms	43412 KB	Output is correct
9	Correct	5187 ms	54860 KB	Output is correct
10	Execution timed out	8034 ms	63704 KB	Time limit exceeded
11	Execution timed out	8035 ms	64132 KB	Time limit exceeded
12	Execution timed out	8035 ms	61560 KB	Time limit exceeded
13	Execution timed out	8084 ms	60916 KB	Time limit exceeded
14	Execution timed out	8016 ms	63704 KB	Time limit exceeded
15	Execution timed out	8034 ms	69100 KB	Time limit exceeded
16	Execution timed out	8021 ms	70288 KB	Time limit exceeded
17	Execution timed out	8050 ms	66364 KB	Time limit exceeded