Submission #722417

#	Time	Username	Problem	Language	Result	Execution time	Memory
722417		Yell0	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	213 ms	47568 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
 
using namespace std;
typedef pair<int,int> pii;
 
int construct(vector<vector<int>> p) {
  int N=p.size();
  vector<pii> comps(N);
  for(int i=0;i<N;++i) comps[i]={-1,-1};
  int newcomp=0;
  vector<int> newsubcomp(N,0);
  for(int i=0;i<N;++i) {
    if(comps[i]==pii(-1,-1)) {
      comps[i]={newcomp,newsubcomp[newcomp]++};
      newcomp++;
    }
    else if(comps[i].second<0) comps[i].second=newsubcomp[comps[i].first]++;
    for(int j=i+1;j<N;++j) {
      if(p[i][j]==3) return 0;
      if(comps[j]==pii(-1,-1)) {
        if(p[i][j]==0) continue;
        if(p[i][j]==1) comps[j]=comps[i];
        if(p[i][j]==2) comps[j].first=comps[i].first;
      } else {
        if(p[i][j]==0&&comps[i].first==comps[j].first) return 0;
        if(p[i][j]==1) {
          if(comps[i].second!=comps[j].second) {
            if(comps[j].second>=0) return 0;
            else comps[j].second=comps[i].second;
          }
        }
        if(p[i][j]==2&&(comps[i]==comps[j]||comps[i].first!=comps[j].first)) return 0;
      }
    }
  }
  for(int i=0;i<N;++i) for(int j=i+1;j<N;++j) {
    if(p[i][j]==0&&comps[i].first==comps[j].first) return 0;
    if(p[i][j]==1&&(comps[i].first!=comps[j].first||(comps[i].second!=comps[j].second&&comps[j].second>=0))) return 0;
    if(p[i][j]==2&&(comps[i]==comps[j]||comps[i].first!=comps[j].first)) return 0;
  }
  vector<vector<vector<int>>> gr(N,vector<vector<int>>(N));
  int i=0;
  for(pii p:comps) gr[p.first][p.second].push_back(i++);
  vector<vector<int>> ans(N,vector<int>(N,0));
  for(int i=0;i<newcomp;++i) {
    if(newsubcomp[i]==2) return 0;
    for(int j=0;j<newsubcomp[i];++j) {
      for(int k=1;k<(int)gr[i][j].size();++k) ans[gr[i][j][k]][gr[i][j][0]]=ans[gr[i][j][0]][gr[i][j][k]]=1;
      if(j==0) ans[gr[i][j][0]][gr[i][newsubcomp[i]-1][0]]=ans[gr[i][newsubcomp[i]-1][0]][gr[i][j][0]]=1;
      else ans[gr[i][j][0]][gr[i][j-1][0]]=ans[gr[i][j-1][0]][gr[i][j][0]]=1;
    }
  }
  for(int i=0;i<N;++i) ans[i][i]=0;
  build(ans);
  return 1;
}

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