Submission #367634

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367634	2021-02-17T19:27:02 Z	dapig	Regions (IOI09_regions)	Java 11	45 / 100	8000 ms	104356 KB

regions

//package eulertour;

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

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 {
				HashMap<Integer, Integer> target = regions[regvals[next]];
				target.put(vis[next]-1, count-1);
			}
		}
	}
	
	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;
	
	HashMap<Integer, Integer>[] 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 HashMap[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 HashMap<>();
			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 < regions.length; i++) {
			HashSet<Integer> hs = new HashSet<>();
			HashMap<Integer, Integer> toReplace = new HashMap<>();
			for (int j = 1; j < newregvals[i].size(); j++) {
				int left = newregvals[i].get(j)-1;
				if (hs.contains(left)) continue;
				int right = regions[i].get(left);
				while (regions[i].containsKey(right)
						&& !hs.contains(right)) {
					hs.add(right);
					right = regions[i].get(right);
				}
				toReplace.put(left, right);
			}
			regions[i] = toReplace;
		}
		
		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 (Entry<Integer, Integer> j : regions[r1].entrySet()) {
				ans += (bs(r2, j.getValue()) - bs(r2, j.getKey()));
			}
			System.out.println(ans);
		}
		
		br.close();

	}

}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	8684 KB	Output is correct
2	Correct	78 ms	8776 KB	Output is correct
3	Correct	104 ms	8572 KB	Output is correct
4	Correct	154 ms	8832 KB	Output is correct
5	Correct	204 ms	9532 KB	Output is correct
6	Correct	365 ms	12012 KB	Output is correct
7	Correct	586 ms	16032 KB	Output is correct
8	Correct	739 ms	21052 KB	Output is correct
9	Correct	982 ms	18440 KB	Output is correct
10	Correct	1163 ms	20528 KB	Output is correct
11	Correct	1514 ms	22064 KB	Output is correct
12	Correct	1493 ms	23436 KB	Output is correct
13	Correct	1630 ms	24788 KB	Output is correct
14	Correct	1765 ms	27108 KB	Output is correct
15	Correct	1927 ms	30812 KB	Output is correct

Subtask #2

30.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8058 ms	44516 KB	Time limit exceeded
2	Execution timed out	8055 ms	41932 KB	Time limit exceeded
3	Execution timed out	8029 ms	52456 KB	Time limit exceeded
4	Correct	1722 ms	29012 KB	Output is correct
5	Correct	1904 ms	32896 KB	Output is correct
6	Correct	4070 ms	40208 KB	Output is correct
7	Correct	4696 ms	46572 KB	Output is correct
8	Correct	4448 ms	64004 KB	Output is correct
9	Correct	6335 ms	78464 KB	Output is correct
10	Execution timed out	8026 ms	94372 KB	Time limit exceeded
11	Execution timed out	8026 ms	94896 KB	Time limit exceeded
12	Execution timed out	8020 ms	87004 KB	Time limit exceeded
13	Execution timed out	8021 ms	85244 KB	Time limit exceeded
14	Execution timed out	8052 ms	90968 KB	Time limit exceeded
15	Execution timed out	8050 ms	100236 KB	Time limit exceeded
16	Execution timed out	8039 ms	104356 KB	Time limit exceeded
17	Execution timed out	8092 ms	102396 KB	Time limit exceeded