oj.uz

답안 #367579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367579 2021-02-17T17:09:41 Z dapig Regions (IOI09_regions) Java 11
0 / 100
 5333 ms 71328 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 {
				Stack<int[]> target = regions[regvals[next]];
				int[] toAdd = new int[] {vis[next]-1, count-1};
				while (!target.isEmpty()) {
					int[] top = target.peek();
					if (top[1] <= toAdd[1] && top[0] >= toAdd[0])
						target.pop();
					else break;
				}
				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;
	
	Stack<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 Stack[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 Stack<>();
			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);
			System.out.flush();
		}
		
		br.close();

	}

}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 8660 KB Output isn't correct
2 Incorrect 74 ms 8668 KB Output isn't correct
3 Incorrect 98 ms 8684 KB Output isn't correct
4 Incorrect 155 ms 8780 KB Output isn't correct
5 Incorrect 202 ms 9472 KB Output isn't correct
6 Incorrect 360 ms 12072 KB Output isn't correct
7 Incorrect 646 ms 19784 KB Output isn't correct
8 Incorrect 741 ms 20020 KB Output isn't correct
9 Incorrect 867 ms 15304 KB Output isn't correct
10 Incorrect 1091 ms 18320 KB Output isn't correct
11 Incorrect 1275 ms 19336 KB Output isn't correct
12 Incorrect 1304 ms 19636 KB Output isn't correct
13 Incorrect 1438 ms 19604 KB Output isn't correct
14 Incorrect 1574 ms 20560 KB Output isn't correct
15 Incorrect 1472 ms 24104 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2291 ms 31068 KB Output isn't correct
2 Incorrect 2714 ms 28032 KB Output isn't correct
3 Incorrect 3148 ms 34744 KB Output isn't correct
4 Incorrect 1426 ms 21588 KB Output isn't correct
5 Incorrect 1725 ms 25316 KB Output isn't correct
6 Incorrect 2051 ms 27040 KB Output isn't correct
7 Incorrect 2534 ms 33124 KB Output isn't correct
8 Incorrect 2506 ms 42260 KB Output isn't correct
9 Incorrect 3520 ms 51000 KB Output isn't correct
10 Incorrect 3989 ms 59408 KB Output isn't correct
11 Incorrect 5333 ms 60352 KB Output isn't correct
12 Incorrect 3054 ms 60656 KB Output isn't correct
13 Incorrect 3345 ms 61504 KB Output isn't correct
14 Incorrect 3945 ms 63408 KB Output isn't correct
15 Incorrect 4375 ms 71120 KB Output isn't correct
16 Incorrect 4295 ms 71328 KB Output isn't correct
17 Incorrect 4229 ms 68000 KB Output isn't correct