Submission #318069

#	Time	Username	Problem	Language	Result	Execution time	Memory
318069		amunduzbaev	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	273 ms	28388 KiB

supertrees

//#include "grader.cpp"
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a) 
const int N = 1e3+5;
vector<vector<int>> p1, b1;
int n1, timer, par[N], used[N], time1[N];
vector <int> c;

void dfs(int u){
	c.pb(u);
	used[u] = 1;
	par[u] = u;
	time1[u] = timer;

	for(int i=0;i<n1;i++){
		if(used[i]) continue; 
		if(p1[u][i] == 1){
			used[i] = 1;
			par[i] = u;
			time1[i] = timer;
			b1[u][i] = b1[i][u] = 1;
		}
	}
	for(int i=0;i<n1;i++){
		if(used[i]) continue;
		if(p1[u][i] == 2) dfs(i);
	}


}

int construct(vector<vector<int>> P) {
	p1 = P;
	n1 = p1.size();
	b1.resize(n1, vector<int>(n1, 0));
	for(int i=0;i<n1;i++){
		if(used[i]) continue;
		dfs(i);
		if(c.size() == 2) return 0;

		else if(c.size() > 2){
			int s = c.size() - 1;
			for(int j=0;j<s; j++){
				b1[c[j]][c[j+1]] = 1;
				b1[c[j+1]][c[j]] = 1;
			}
			b1[c[0]][c[s]] = 1;
			b1[c[s]][c[0]] = 1;
		}
		timer ++;
		c.clear();
	}

	for(int i=0;i<n1;i++){
		for(int j=0;j<n1;j++){
			if(par[i] == par[j] && p1[i][j] != 1) return 0;
            if(time1[i] == time1[j] && par[i] != par[j] && p1[i][j] != 2) return 0;
            if(time1[i] != time1[j] && p1[i][j]) return 0;
        }
	}
	build(b1);
	return 1;
}

/*
5
0 2 2 2 2
2 0 2 2 2
2 2 0 2 2
2 2 2 0 2 
2 2 2 2 0
3
1 2 2
2 1 2
2 2 1
4
1 1 2 2 
1 1 2 2 
2 2 1 2 
2 2 2 1 
5
1 2 2 2 0
2 1 2 2 0
2 2 1 2 0
2 2 2 1 0
0 0 0 0 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