Submission #831825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831825	2023-08-20T15:47:52 Z	gesgha	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	193 ms	22056 KB

supertrees

#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);
			if (vis[j]) return 0;
			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;
		}
		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 < 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++) {
				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	1 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	1092 KB	Output is correct
7	Correct	150 ms	22056 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	1 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	1092 KB	Output is correct
7	Correct	150 ms	22056 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	8 ms	1108 KB	Output is correct
13	Correct	151 ms	22036 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	63 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	37 ms	5764 KB	Output is correct
21	Correct	153 ms	21964 KB	Output is correct
22	Correct	150 ms	22020 KB	Output is correct
23	Correct	186 ms	22052 KB	Output is correct
24	Correct	159 ms	22032 KB	Output is correct
25	Incorrect	150 ms	22020 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

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

Subtask #4
35.0 / 35.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	38 ms	5736 KB	Output is correct
5	Correct	151 ms	22016 KB	Output is correct
6	Correct	151 ms	22016 KB	Output is correct
7	Correct	158 ms	22032 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	38 ms	5700 KB	Output is correct
10	Correct	171 ms	22020 KB	Output is correct
11	Correct	166 ms	22016 KB	Output is correct
12	Correct	193 ms	22020 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	38 ms	5760 KB	Output is correct
17	Correct	154 ms	21996 KB	Output is correct
18	Correct	154 ms	22012 KB	Output is correct
19	Correct	156 ms	22016 KB	Output is correct
20	Correct	152 ms	22020 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	1 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	1092 KB	Output is correct
7	Correct	150 ms	22056 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	8 ms	1108 KB	Output is correct
13	Correct	151 ms	22036 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	63 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	37 ms	5764 KB	Output is correct
21	Correct	153 ms	21964 KB	Output is correct
22	Correct	150 ms	22020 KB	Output is correct
23	Correct	186 ms	22052 KB	Output is correct
24	Correct	159 ms	22032 KB	Output is correct
25	Incorrect	150 ms	22020 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	1 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	1092 KB	Output is correct
7	Correct	150 ms	22056 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	8 ms	1108 KB	Output is correct
13	Correct	151 ms	22036 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	63 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	37 ms	5764 KB	Output is correct
21	Correct	153 ms	21964 KB	Output is correct
22	Correct	150 ms	22020 KB	Output is correct
23	Correct	186 ms	22052 KB	Output is correct
24	Correct	159 ms	22032 KB	Output is correct
25	Incorrect	150 ms	22020 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Submission #831825

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 35.0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0