제출 #335804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335804		Agnimandur	슈퍼트리 잇기 (IOI20_supertrees)	Java	61 / 100	1075 ms	40716 KiB

supertrees

import java.util.*;

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;
  }
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4