oj.uz

Submission #831872

# Submission time Handle Problem Language Result Execution time Memory
831872 2023-08-20T16:32:34 Z gesgha Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 189 ms 22312 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 cnt[M][4];

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);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt[i][p[i][j]]++;
		}
	}
	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);
			if (vis[j]) return 0;
			w2 |= (p[i][j] == 2);
		}
		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;
		}
		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 (p[x][j] == 1) {
						palka.pb(j);
						if (used[j]) return 0;
					}
				}
				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 < sz(ids); i++) {
				// if (cnt[ids[i]][1] != sz(ids)) return 0;
				// if (cnt[ids[i]][0] != n - sz(ids)) return 0;
				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++) {
				answer[ids[i]][ids[i + 1]] = 1;
				answer[ids[i + 1]][ids[i]] = 1;
			}
		}
		for (auto x : ids) vis[x] = 1;
	}
	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 1 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 6 ms 1108 KB Output is correct
7 Correct 186 ms 22104 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 1 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 6 ms 1108 KB Output is correct
7 Correct 186 ms 22104 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 1188 KB Output is correct
13 Correct 147 ms 22172 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 62 ms 12196 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 37 ms 5684 KB Output is correct
21 Correct 148 ms 22092 KB Output is correct
22 Correct 148 ms 22156 KB Output is correct
23 Correct 147 ms 22284 KB Output is correct
24 Correct 167 ms 22080 KB Output is correct
25 Incorrect 165 ms 22188 KB Answer gives possible 1 while actual possible 0
26 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 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 37 ms 5676 KB Output is correct
5 Correct 147 ms 22156 KB Output is correct
6 Correct 181 ms 22180 KB Output is correct
7 Correct 148 ms 22300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 38 ms 5672 KB Output is correct
10 Correct 189 ms 22276 KB Output is correct
11 Correct 159 ms 22304 KB Output is correct
12 Correct 167 ms 22244 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 40 ms 5732 KB Output is correct
17 Correct 172 ms 22312 KB Output is correct
18 Correct 171 ms 22220 KB Output is correct
19 Correct 163 ms 22292 KB Output is correct
20 Correct 164 ms 22228 KB Output is correct

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 1 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 6 ms 1108 KB Output is correct
7 Correct 186 ms 22104 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 1188 KB Output is correct
13 Correct 147 ms 22172 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 62 ms 12196 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 37 ms 5684 KB Output is correct
21 Correct 148 ms 22092 KB Output is correct
22 Correct 148 ms 22156 KB Output is correct
23 Correct 147 ms 22284 KB Output is correct
24 Correct 167 ms 22080 KB Output is correct
25 Incorrect 165 ms 22188 KB Answer gives possible 1 while actual possible 0
26 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 1 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 6 ms 1108 KB Output is correct
7 Correct 186 ms 22104 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 1188 KB Output is correct
13 Correct 147 ms 22172 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 62 ms 12196 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 37 ms 5684 KB Output is correct
21 Correct 148 ms 22092 KB Output is correct
22 Correct 148 ms 22156 KB Output is correct
23 Correct 147 ms 22284 KB Output is correct
24 Correct 167 ms 22080 KB Output is correct
25 Incorrect 165 ms 22188 KB Answer gives possible 1 while actual possible 0
26 Halted 0 ms 0 KB -