Submission #722389

#	Time	Username	Problem	Language	Result	Execution time	Memory
722389		Yell0	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	340 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].first!=comps[j].first) return 0;
          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]) return 0;
      }
    }
  }
  vector<vector<vector<int>>> gr(N,vector<vector<int>>(N));
  for(pii p:comps) gr[p.first][p.second].push_back(p.first);
  vector<vector<int>> ans(N,vector<int>(N,0));
  for(int i=0;i<N;++i) {
    for(int j=0;j<N;++j) {
      for(int k=1;k<gr[i][j].size();++k) ans[gr[i][j][k]][gr[i][j][0]]=ans[gr[i][j][k]][gr[i][j][0]]=1;
      ans[gr[i][j][0]][gr[i][(j-1+N)%N][0]]=ans[gr[i][(j-1+N)%N][0]][gr[i][j][0]]=1;
    }
  }
  build(ans);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       for(int k=1;k<gr[i][j].size();++k) ans[gr[i][j][k]][gr[i][j][0]]=ans[gr[i][j][k]][gr[i][j][0]]=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