oj.uz

Submission #482717

# Submission time Handle Problem Language Result Execution time Memory
482717 2021-10-26T06:35:45 Z PoPularPlusPlus Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 214 ms 26260 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);
		}
	}
	for(int i = 0; i < (int)v1.size(); i++){
		if(i == (int)v1.size()-1){
			if(i!=0){
				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][0]);
			adj[v1[i][0]].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
11.0 / 11.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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1392 KB Output is correct
7 Correct 214 ms 26008 KB Output is correct

Subtask #2
0 / 10.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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1392 KB Output is correct
7 Correct 214 ms 26008 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 7 ms 1356 KB Output is correct
13 Correct 179 ms 26068 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 #3
0 / 19.0

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

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 44 ms 6804 KB Output is correct
5 Correct 189 ms 26088 KB Output is correct
6 Correct 176 ms 26036 KB Output is correct
7 Correct 177 ms 26036 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 53 ms 6832 KB Output is correct
10 Correct 170 ms 26036 KB Output is correct
11 Correct 171 ms 26004 KB Output is correct
12 Correct 176 ms 26044 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 45 ms 6780 KB Output is correct
17 Correct 187 ms 26260 KB Output is correct
18 Correct 184 ms 26080 KB Output is correct
19 Correct 169 ms 26100 KB Output is correct
20 Correct 175 ms 26060 KB Output is correct

Subtask #5
0 / 21.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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1392 KB Output is correct
7 Correct 214 ms 26008 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 7 ms 1356 KB Output is correct
13 Correct 179 ms 26068 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 #6
0 / 4.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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 8 ms 1392 KB Output is correct
7 Correct 214 ms 26008 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 7 ms 1356 KB Output is correct
13 Correct 179 ms 26068 KB Output is correct
14 Incorrect 1 ms 332 KB WA in grader: Invalid return value of construct
15 Halted 0 ms 0 KB -