제출 #261206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261206		idk321	Split the Attractions (IOI19_split)	Java	22 / 100	1219 ms	53176 KiB

split

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

class split {
	ArrayList<Integer>[] adj;
	int a;
	int b;
	int n;
	int treeNodeA;
	int treeNodeB;
	int[] subtreeSize;
	int[] groups;

	public int[] find_split(int n, int a, int b, int c, int[] p, int[] q) {

		this.n = n;
		groups = new int[n];
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();
		for (int i = 0; i < p.length; i++) {
			int x = p[i];
			int y = q[i];
			adj[x].add(y);
			adj[y].add(x);
		}

		if (n == p.length + 1) {
			int orgA = a;
			int orgB = b;
			int orgC = c;
			int[][] ar = {{1, a}, {2, b}, {3, c}};
			Arrays.sort(ar, new ArrayComparator());
			this.a = ar[0][1];
			this.b = ar[1][1];
			subtreeSize = new int[n];
			buildTree(0, -1);
			treeNodeA = -1;
			treeNodeB = -1;
			findParts(0, -1);
			if (treeNodeA == -1 || treeNodeB == -1) return groups;

			Arrays.fill(groups, ar[2][0]);
			markNodeA(treeNodeA, treeNodeB, ar[0][0]);
			markNodeB(treeNodeB, treeNodeA, ar[1][0]);
		}

		return groups;
	}

	private static class ArrayComparator implements Comparator<int[]> {
		@Override
		public int compare(int[] o1, int[] o2) {
			return Integer.compare(o1[1], o2[1]);
		}
	}

	private void buildTree(int node, int parent) {
		for (int adjacent : adj[node]) {
			if (adjacent == parent) continue;
			buildTree(adjacent, node);
			subtreeSize[node] += subtreeSize[adjacent];
		}
		subtreeSize[node]++;
	}

	private void markNodeA(int node, int parent, int group) {
		if (a == 0) return;
		groups[node] = group;
		a--;
		for (int adjacent : adj[node]) {
			if (adjacent == parent) continue;
			markNodeA(adjacent, node, group);
		}
	}

	private void markNodeB(int node, int parent, int group) {
		if (b == 0) return;
		groups[node] = group;
		b--;
		for (int adjacent : adj[node]) {
			if (adjacent == parent) continue;
			markNodeB(adjacent, node, group);
		}
	}

	private void findParts(int node, int parent) {
		for (int adjacent : adj[node]) {
			if (adjacent == parent) continue;
			if (subtreeSize[adjacent] >= a) {
				if (n - subtreeSize[adjacent] >= b) {
					treeNodeA = adjacent;
					treeNodeB = node;
				}
			}
			if (subtreeSize[adjacent] >= b) {
				if (n - subtreeSize[adjacent] >= a) {
					treeNodeA = node;
					treeNodeB = adjacent;
				}
			}
			findParts(adjacent, node);
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Note: split.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36