Submission #303760

#	Time	Username	Problem	Language	Result	Execution time	Memory
303760		Hemimor	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	287 ms	30168 KiB

supertrees

#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,N;
vvi p,c,g,G;
vi b,vis,ind;

void dfs(int v,int t){
	vis[v]=1;
	ind[v]=t;
	b.push_back(v);
	for(int i=0;i<n;i++) if(i!=v&&p[v][i]==1&&!vis[i]) dfs(i,t);
}

void DFS(int v){
	vis[v]=1;
	b.push_back(v);
	for(int i=0;i<N;i++) if(i!=v&&G[v][i]==1&&!vis[i]) DFS(i);
}

int construct(vvi p_){
	p=p_;
	n=p.size();
	vis=ind=vi(n);
	g=vvi(n,vi(n));
	int id=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(p[i][j]==3) return 0;
	for(int i=0;i<n;i++) if(!vis[i]){
		b.clear();
		dfs(i,id);
		int m=b.size();
		for(auto v:b) for(auto u:b) if(p[u][v]!=1) return 0;
		for(int j=1;j<m;j++){
			int u=b[j-1],v=b[j];
			g[u][v]=g[v][u]=1;
		}
		id++;
		c.push_back(b);
	}
	N=c.size();
	G=vvi(N,vi(N));
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j]==2){
		int u=ind[i],v=ind[j];
		G[u][v]=G[v][u]=1;
	}
	vis=vi(N);
	for(int i=0;i<N;i++) if(!vis[i]){
		b.clear();
		DFS(i);
		int m=b.size();
		for(auto I:b) for(auto J:b) if(I<J){
			for(auto u:c[I]) for(auto v:c[J]) if(p[u][v]!=2) return 0;
		}
		if(m==1) continue;
		if(m==2) return 0;
		for(int j=0;j<m;j++){
			int u=c[b[j]][0],v=c[b[(j+1)%m]][0];
			g[u][v]=g[v][u]=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