oj.uz

Submission #839158

# Submission time Handle Problem Language Result Execution time Memory
839158 2023-08-28T22:01:33 Z tranxuanbach Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 304 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

const int N = 1e3 + 5;

int n;
vector <vector <int>> cnt_path;

vector <vector <int>> adj;

bool check_clique(const vector <int>& a, int l, int r){
	for (auto u: a){
		for (auto v: a){
			if (u >= v){
				continue;
			}
			if (not (l <= cnt_path[u][v] and cnt_path[u][v] <= r)){
				return false;
			}
		}
	}
	return true;
}

vector <bool> vis;

void dfs(int u, int l, int r, vector <int>& a){
	vis[u] = true;
	a.emplace_back(u);
	for (int v = 0; v < n; v++){
		if (not vis[v] and l <= cnt_path[u][v] and cnt_path[u][v] <= r){
			dfs(v, l, r, a);
		}
	}
}

vector <bool> is_end;

int construct(vector <vector <int>> _p){
	n = isz(_p);
	cnt_path = _p;

	adj.assign(n, vector <int>(n, 0));
	vis.assign(n, false);
	is_end.assign(n, false);

	for (int u = 0; u < n; u++){
		if (vis[u]){
			continue;
		}
		vector <int> a;
		dfs(u, 1, 1, a);
		if (not check_clique(a, 1, 1)){
			return 0;
		}
		for (int i = 0; i + 1 < isz(a); i++){
			int u = a[i], v = a[i + 1];
			adj[u][v] = adj[v][u] = 1;
		}
		is_end[a.back()] = true;
	}

	vis.assign(n, false);
	for (int u = 0; u < n; u++){
		if (vis[u]){
			continue;
		}
		vector <int> a;
		dfs(u, 1, 2, a);
		if (not check_clique(a, 1, 2)){
			return 0;
		}
		vector <int> b;
		for (auto u: a){
			if (is_end[u]){
				b.emplace_back(u);
			}
		}
		if (isz(a) == 1){
			continue;
		}
		for (int i = 0; i < isz(a); i++){
			int u = a[i], v = a[(i + 1) % isz(a)];
			adj[u][v] = adj[v][u] = 1;
		}
	}

	for (int u = 0; u < n; u++){
		for (int v = 0; v < n; v++){
			if (cnt_path[u][v] == 3){
				return 0;
			}
		}
	}

	build(adj);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Too many ways to get from 1 to 4, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -