oj.uz

답안 #367634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367634 2021-02-17T19:27:02 Z dapig Regions (IOI09_regions) Java 11
45 / 100
 8000 ms 104356 KB 
//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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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