Submission #839363

#	Time	Username	Problem	Language	Result	Execution time	Memory
839363		epicci23	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	164 ms	24184 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()


const int N = 1005;

int par[N];
int siz[N];

int find(int a)
{
  if(par[a]==a) return a;
  return par[a]=find(par[a]);
}

void unite(int a,int b)
{
  a=find(a),b=find(b);
  if(a==b) return;
  if(siz[a]>siz[b]) swap(a,b);
  siz[b]+=siz[a];
  par[a]=b;
}

int construct(vector<vector<int>> p) {
  iota(par,par+N,0LL);
  fill(siz,siz+N,1LL);
    
    int n = p[0].size();
    vector<vector<int>> g(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        if(p[i][j]) unite(i,j);
    
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        if(!p[i][j] && find(i)==find(j))
          return 0;
        

    vector<int> no[n];
    for(int i=0;i<n;i++) no[find(i)].pb(i);

    for(int xd=0;xd<n;xd++)
    {
      if(no[xd].size()<=1) continue;
      int m = no[xd].size();
      vector<int> zort(4,0);
      vector<int> v[m];
      for(int i=0;i<m;i++)
      {
        for(int j=i;j<m;j++)
        {
          if(i==j)
          {
            v[i].pb(i);
            continue;
          }
          int a=no[xd][i];
          int b=no[xd][j];
          if(p[a][b]==1)
          {
            v[i].pb(j);
            v[j].pb(i); 
          }
          zort[p[a][b]]=1;
        }
      }
      if(zort[2] && zort[3]) return 0;
      for(int i=0;i<m;i++) sort(all(v[i]));
      vector<int> tems;
      vector<int> vis(m,0LL); 
      for(int i=0;i<m;i++)
      {
       if(vis[i]) continue;
       tems.pb(i);
       for(int x:v[i])
       {
        if(vis[x]) return 0;
        vis[x]=1; 
        if(v[i]!=v[x]) return 0;
       }
       for(int j=1;j<sz(v[i]);j++)
       {
        int a=no[xd][v[i][j]];
        int b=no[xd][v[i][j-1]];
        g[a][b]=g[b][a]=1;
       }
      }
      int k=sz(tems);
      if(k==2 && zort[2]) return 0;
      if(k>2 && zort[2])
      {
       for(int i=1;i<k;i++)
       { 
        g[no[xd][tems[i]]][no[xd][tems[i-1]]]=1;
        g[no[xd][tems[i-1]]][no[xd][tems[i]]]=1;
       } 
       g[no[xd][tems[k-1]]][no[xd][tems[0]]]=1;
       g[no[xd][tems[0]]][no[xd][tems[k-1]]]=1;
      }
      if(zort[3] && k!=4) return 0;
      if(zort[3])
      {
       for(int i=1;i<k;i++)
       { 
        g[no[xd][tems[i]]][no[xd][tems[i-1]]]=1;
        g[no[xd][tems[i-1]]][no[xd][tems[i]]]=1;
       } 
       g[no[xd][tems[k-1]]][no[xd][tems[0]]]=1;
       g[no[xd][tems[0]]][no[xd][tems[k-1]]]=1;
       g[no[xd][tems[0]]][no[xd][tems[2]]]=1;
       g[no[xd][tems[2]]][no[xd][tems[0]]]=1;
      }
    }
  build(g);
  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