Submission #303261

#	Time	Username	Problem	Language	Result	Execution time	Memory
303261		Utaha	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	272 ms	26232 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
// typedef long double ld;

#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define REP(i,n) for(int i=0;i<(n);i++)
#define MP make_pair
#define pb push_back
#define eb emplace_back
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
const ll INF64 = 1e18;
const ll MOD = ll(1e9+7);


int n;
vector<int> cmp;
bool vis[maxn];
std::vector<std::vector<int>> ans;
std::vector<std::vector<int>> p;

void dfs(int u){
	vis[u]=1;
	cmp.pb(u);
	REP(v,n) if(v!=u&&p[u][v]&&!vis[v]){
		dfs(v);
	}
}	

vector<int> _;
bool vis2[maxn];

void dfs2(int u){
	vis2[u]=1;
	_.pb(u);
	REP(v,n) if(v!=u&&p[u][v]==1&&!vis2[v]){
		dfs2(v);
	}
}


void add(int x,int y){
	ans[x][y]=ans[y][x]=1;
}

bool process(){
	// cout<<"process: ";
	// for(int i:cmp){
		// cout<<i<<' ';
	// }
	// cout<<'\n';

	for(int i:cmp) vis2[i] = 0;

	vector<int> ring;

	for(int i:cmp) if(!vis2[i]){
		_.clear();
		dfs2(i);
		// for(int j:_){
			// cout<<j<<' ';
		// }
		// cout<<endl;

		for(int x:_) for(int y:_){
			if(p[x][y]!=1) return 0;
		}
		REP(i,SZ(_)-1){
			add(_[i],_[i+1]);
		}
		ring.pb(_[0]);
	}
	if(SZ(ring)==2){
		return 0;
	}
	if(SZ(ring)>2){
		ring.pb(ring[0]);
		REP(i,SZ(ring)-1){
			add(ring[i],ring[i+1]);
		}
	}
	return 1;
}

int construct(std::vector<std::vector<int>> A) {
	p=A;
	n = p.size();
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}

	REP(i,n) REP(j,n) if(p[i][j]==3) return 0;
	bool flag = 1;
	REP(i,n) if(!vis[i]){
		cmp.clear();
		dfs(i);
		flag &= process();
		if(!flag) return 0;
	}
	build(ans);
	return 1;
}

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