| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 335800 | Agnimandur | 슈퍼트리 잇기 (IOI20_supertrees) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//public class supertrees
public class supertrees {
public int construct(int[][] p) {
int N = p.length;
for (int[] i: p) {
for (int j: i) {
if (j==3) return 0;
}
}
for (int i = 0; i < N; i++) {
if (p[i][i] != 1) return 0;
}
int[][] ans = new int[N][N];
boolean[] vis = new boolean[N];
boolean[] vis2 = new boolean[N];
ArrayDeque<Integer> bfs = new ArrayDeque<Integer>();
for (int r = 0; r < N; r++) {
if (vis[r])continue;
ArrayList<Integer> comp = new ArrayList<Integer>();
bfs.add(r);
vis[r] = true;
while (!bfs.isEmpty()) {
int i = bfs.pollFirst();
comp.add(i);
for (int j = 0; j < N; j++) {
if (!vis[j] && p[i][j] > 0) {
vis[j] = true;
bfs.add(j);
}
}
}
for (int i = 0; i < comp.size(); i++) {
for (int j = i+1; j < comp.size(); j++) {
if (p[comp.get(i)][comp.get(j)]==0)return 0;
}
}
ArrayList<Integer> cyc = new ArrayList<Integer>();
for (int c: comp) {
if (vis2[c])continue;
cyc.add(c);
vis2[c] = true;
bfs.add(c);
ArrayList<Integer> sub = new ArrayList<Integer>();
while (!bfs.isEmpty()) {
int i = bfs.pollFirst();
sub.add(i);
for (int j: comp) {
if (!vis2[j] && p[i][j]==1) {
vis2[j] = true;
bfs.add(j);
}
}
}
for (int ind = 1; ind < sub.size(); ind++) {
int i = sub.get(ind-1);
int j = sub.get(ind);
if (i==j)continue;
ans[i][j] = 1;
ans[j][i] = 1;
}
for (int i = 0; i < sub.size(); i++) {
for (int j = i+1; j < sub.size(); j++) {
if (p[sub.get(i)][sub.get(j)]==2) return 0;
}
}
}
for (int ind = 0; ind < cyc.size(); ind++) {
int i = cyc.get(ind);
int j = cyc.get((ind+1)%cyc.size());
if (i==j)continue;
ans[i][j] = 1;
ans[j][i] = 1;
}
if (cyc.size()==2)return 0;
for (int i = 0; i < cyc.size(); i++) {
for (int j = i+1; j < cyc.size(); j++) {
if (p[cyc.get(i)][cyc.get(j)]==1) return 0;
}
}
}
grader.build(ans);
return 1;
}
}