oj.uz

답안 #367602

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

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

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