Submission #335793

#	Time	Username	Problem	Language	Result	Execution time	Memory
335793		Agnimandur	Connecting Supertrees (IOI20_supertrees)	Java	0 / 100	80 ms	8552 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: comp) {
        for (int j: comp) {
          if (p[i][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: sub) {
          for (int j: sub) {
            if (p[i][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;
      }
      for (int i: cyc) {
        for (int j: cyc) {
          if (p[i][j]==1) return 0;
        }
      }
    }
    
    grader.build(ans);
    return 1;
  }
}

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