Submission #367634

#	Time	Username	Problem	Language	Result	Execution time	Memory
367634		dapig	Regions (IOI09_regions)	Java	45 / 100	8092 ms	104356 KiB

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 / 15
• Subtask 2: 30 / 85