oj.uz

Submission #831821

# Submission time Handle Problem Language Result Execution time Memory
831821 2023-08-20T15:46:09 Z gesgha Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 157 ms 22016 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
 
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
 
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector <T>;
 
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
 
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e6 + 10;
const int M = 3e3 + 100;
const int mod = 1e9 + 7;
const bool TEST = 1;
 
 
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	ve <bool> vis(n, 0);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		ve <int> ids;
		bool w2 = 0;
		for (int j = 0; j < n; j++) if (p[i][j]) {
			ids.pb(j);
			w2 |= (p[i][j] == 1);
		}
		for (int i = 0; i < sz(ids) - 1; i++) {
			for (int j = 0; j < sz(ids) - 1; j++) {
				if (!p[ids[i]][ids[j]]) return 0;
			}
		}
		for (int i = 0; i < sz(ids); i++) {
			for (int j = 0; j < sz(ids); j++) if (p[ids[i]][ids[j]] != 1) return 0;
		}
		for (int i = 0; i < sz(ids) - 1; i++) {
			vis[ids[i]] = 1;
          	vis[ids[i + 1]] = 1;
			answer[ids[i]][ids[i + 1]] = 1;
			answer[ids[i + 1]][ids[i]] = 1;
		}
		// if(w2) {
		// 	ve <ve <int>> palki;
		// 	ve <bool> used(n);
		// 	for (auto x : ids) {
		// 		if (used[x])continue;
		// 		ve <int> palka;
		// 		for (int j = 0; j < n; j++) {
		// 			if (used[j]) continue;
		// 			if (p[x][j] == 1) palka.pb(j);
		// 		}
		// 		palki.pb(palka);
		// 		for (int j = 0; j < sz(palka); j++) used[palka[j]] = 1;
		// 		for (int i = 0; i < sz(palka) - 1; i++) {
		// 			answer[palka[i]][palka[i + 1]] = 1;
		// 			answer[palka[i + 1]][palka[i]] = 1;
		// 		}
		// 	}
		// 	for (int i = 0; i < sz(palki); i++) {
		// 		for (auto x : palki[i]) {
		// 			for (auto y : palki[i]) if (p[x][y] != 1) return 0;
		// 		}
		// 	}
		// 	for (int i = 0; i < sz(palki) - 1; i++) {
		// 		answer[palki[i][0]][palki[i + 1][0]] = 1;
		// 		answer[palki[i + 1][0]][palki[i][0]] = 1;
		// 	}
		// 	answer[palki[0][0]][palki[sz(palki) - 1][0]] = 1;
		// 	answer[palki[sz(palki) - 1][0]][palki[0][0]] = 1;
		// } else {
		// }
	}
	for (int i = 0; i < n; i++) answer[i][i] = 0;
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 157 ms 22016 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 157 ms 22016 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 232 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 156 ms 21964 KB Output is correct
14 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
0 / 35.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 157 ms 22016 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 232 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 156 ms 21964 KB Output is correct
14 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 157 ms 22016 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 232 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 156 ms 21964 KB Output is correct
14 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -