oj.uz

답안 #367591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367591 2021-02-17T17:44:54 Z dapig Regions (IOI09_regions) Java 11
0 / 100
 5083 ms 71212 KB 
//package eulertour;

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 81 ms 8556 KB Output isn't correct
2 Incorrect 77 ms 8640 KB Output isn't correct
3 Incorrect 97 ms 8704 KB Output isn't correct
4 Incorrect 147 ms 8848 KB Output isn't correct
5 Incorrect 192 ms 9452 KB Output isn't correct
6 Incorrect 356 ms 11944 KB Output isn't correct
7 Incorrect 664 ms 19908 KB Output isn't correct
8 Incorrect 714 ms 20260 KB Output isn't correct
9 Incorrect 903 ms 15336 KB Output isn't correct
10 Incorrect 1031 ms 18420 KB Output isn't correct
11 Incorrect 1227 ms 19296 KB Output isn't correct
12 Incorrect 1305 ms 19752 KB Output isn't correct
13 Incorrect 1342 ms 19756 KB Output isn't correct
14 Incorrect 1459 ms 20832 KB Output isn't correct
15 Incorrect 1500 ms 24044 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2271 ms 31016 KB Output isn't correct
2 Incorrect 2577 ms 28076 KB Output isn't correct
3 Incorrect 3181 ms 34828 KB Output isn't correct
4 Incorrect 1472 ms 21832 KB Output isn't correct
5 Incorrect 1649 ms 25416 KB Output isn't correct
6 Incorrect 2080 ms 27224 KB Output isn't correct
7 Incorrect 2593 ms 33136 KB Output isn't correct
8 Incorrect 2424 ms 42052 KB Output isn't correct
9 Incorrect 3274 ms 51148 KB Output isn't correct
10 Incorrect 3738 ms 59252 KB Output isn't correct
11 Incorrect 5083 ms 60456 KB Output isn't correct
12 Incorrect 2868 ms 60728 KB Output isn't correct
13 Incorrect 3169 ms 61688 KB Output isn't correct
14 Incorrect 3872 ms 63472 KB Output isn't correct
15 Incorrect 4158 ms 71212 KB Output isn't correct
16 Incorrect 4238 ms 71196 KB Output isn't correct
17 Incorrect 4373 ms 67968 KB Output isn't correct