oj.uz

Submission #482728

# Submission time Handle Problem Language Result Execution time Memory
482728 2021-10-26T07:01:01 Z PoPularPlusPlus Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 179 ms 28092 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

/*void build(vector<vector<int>>& ans){
	for(int i = 0; i < (int)ans.size(); i++){
		for(int j = 0; j < (int)ans.size(); j++)cout << ans[i][j] << ' ';
		cout << '\n';
	}
}*/

struct UFDS {

vector<int> p,siz;

void init(int n){
	p.resize(n + 3);
	siz.resize(n + 3);
	for(int i = 0; i <= n; i++){
		p[i] = i;
		siz[i] = 1;
	}
}

int get(int x){
	return p[x]=(x==p[x] ? x : get(p[x]));
}

void unio(int u , int v){
	int a = get(u);
	int b=get(v);
	if(a==b)return;
	if(siz[a]>siz[b])swap(a,b);
	p[b]=a;
	siz[a]+=siz[b];
}
};

vector<vector<int>> b;

vector<int> adj[2003];

int help(vector<int>& v){
	UFDS uf;
	int n = v.size();
	uf.init(n + 2);
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n;j++){
			if(b[v[i]][v[j]] == 1){
				uf.unio(i,j);
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(uf.get(i) == uf.get(j) && b[v[i]][v[j]] == 2)return -1;
		}
	}
	vector<vector<int>> v1;
	bool vis1[n + 1];
	memset(vis1,0,sizeof vis1);
	for(int i = 0; i < n; i++){
		if(!vis1[i]){
			vector<int> x;
			x.pb(v[i]);
			vis1[i] = 1;
			for(int j = i+1; j < n; j++){
				if(uf.get(i) == uf.get(j)){
					x.pb(v[j]);
					vis1[j] = 1;
				}
			}
			v1.pb(x);
		}
	}
	if(v.size() == 2)return -1;
	for(int i = 0; i < (int)v1.size(); i++){
		if(i == (int)v1.size()-1){
			if(i!=0 && i!=1){
				adj[v1[i][0]].pb(v1[0][0]);
				adj[v1[0][0]].pb(v1[i][0]);
			}
		}
		else {
			adj[v1[i][0]].pb(v1[i + 1][0]);
			adj[v1[i+1][0]].pb(v1[i][0]);
		}
	}
	for(int i = 0; i < (int)v1.size(); i++){
		for(int j = 1; j < (int)v1[i].size(); j++){
			adj[v1[i][j]].pb(v1[i][j-1]);
			adj[v1[i][j-1]].pb(v1[i][j]);
		}
	}
	return 1;
}

int construct(std::vector<std::vector<int>> v){
	int n = v.size();
	UFDS d;
	b = v;
	d.init(n + 2);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(v[i][j]!=0)d.unio(i,j);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i + 1 ;j < n; j++){
			if(v[i][j] == 0 && d.get(i) == d.get(j))return -1;
		}
	}

	vector<vector<int>> com;
	bool vis[n + 1];
	memset(vis,0,sizeof vis);
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			vector<int> x;
			x.pb(i);
			vis[i] = 1;
			for(int j = i+1; j < n; j++){
				if(d.get(i) == d.get(j)){
					x.pb(j);
					vis[j] = 1;
				}
			}
			com.pb(x);
		}
	}
	vector<vector<int>> ans(n,vector<int> (n,0));
	for(int i = 0; i < (int)com.size(); i++){
		int x = help(com[i]);
		if(x == -1)return 0;
	}
	for(int i = 0; i < n; i++){
		for(int j : adj[i]){
			ans[i][j] = 1;
		}
	}
	build(ans);
	return 1;
}
/*
void solve(){
	int n;
	cin >> n;
	vector<vector<int>> t(n,vector<int>(n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)cin >> t[i][j];
	}
	construct(t);
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 1476 KB Output is correct
9 Correct 179 ms 27944 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 8 ms 1484 KB Output is correct
13 Correct 178 ms 28092 KB Output is correct
14 Incorrect 1 ms 332 KB WA in grader: Invalid return value of construct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 45 ms 6824 KB Output is correct
5 Correct 174 ms 26000 KB Output is correct
6 Incorrect 97 ms 16056 KB Answer gives possible 0 while actual possible 1
7 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -