Submission #839267

#	Time	Username	Problem	Language	Result	Execution time	Memory
839267		epicci23	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	187 ms	22224 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
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<vector<int>> v[m];
      set<int> s;
      vector<int> deg(m,0);
      for(int i=0;i<m;i++)
      {
      	for(int j=i+1;j<m;j++)
      	{
      	  if(i==j) continue;
          if(p[i][j]==2)
          {
            s.insert(i);
            s.insert(j);
            deg[i]++;
            deg[j]++;
          }
      	}
      }
      int k=s.size();
      if(k==2) return 0;
      for(int x:s) if(deg[x]!=k-1) return 0;
      if(k>0)
      {
       int a=*s.begin();
       int b=*s.rbegin();
       g[a][b]=g[b][a]=1;
      }
      for(int i=1;i<m;i++) 
      	g[no[xd][i]][no[xd][i-1]]=g[no[xd][i-1]][no[xd][i]]=1;
    }
    build(g);
	return 1;
}

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