Submission #831811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831811	2023-08-20T15:38:59 Z	gesgha	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	1000 ms	22032 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);
			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]] == 0) 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 (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	12 ms	1108 KB	Output is correct
7	Correct	799 ms	22012 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	12 ms	1108 KB	Output is correct
7	Correct	799 ms	22012 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1180 KB	Output is correct
13	Correct	159 ms	22032 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	72 ms	12036 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	40 ms	5744 KB	Output is correct
21	Correct	175 ms	21948 KB	Output is correct
22	Correct	158 ms	21964 KB	Output is correct
23	Correct	331 ms	22032 KB	Output is correct
24	Correct	158 ms	22028 KB	Output is correct
25	Incorrect	176 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	272 KB	Output is correct
4	Incorrect	212 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-

Subtask #4
0 / 35.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	41 ms	5760 KB	Output is correct
5	Correct	171 ms	22012 KB	Output is correct
6	Correct	171 ms	22020 KB	Output is correct
7	Correct	335 ms	21948 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	50 ms	5768 KB	Output is correct
10	Correct	424 ms	22000 KB	Output is correct
11	Correct	173 ms	22016 KB	Output is correct
12	Execution timed out	1087 ms	12168 KB	Time limit exceeded
13	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	12 ms	1108 KB	Output is correct
7	Correct	799 ms	22012 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1180 KB	Output is correct
13	Correct	159 ms	22032 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	72 ms	12036 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	40 ms	5744 KB	Output is correct
21	Correct	175 ms	21948 KB	Output is correct
22	Correct	158 ms	21964 KB	Output is correct
23	Correct	331 ms	22032 KB	Output is correct
24	Correct	158 ms	22028 KB	Output is correct
25	Incorrect	176 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	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	12 ms	1108 KB	Output is correct
7	Correct	799 ms	22012 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1180 KB	Output is correct
13	Correct	159 ms	22032 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	72 ms	12036 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	40 ms	5744 KB	Output is correct
21	Correct	175 ms	21948 KB	Output is correct
22	Correct	158 ms	21964 KB	Output is correct
23	Correct	331 ms	22032 KB	Output is correct
24	Correct	158 ms	22028 KB	Output is correct
25	Incorrect	176 ms	22020 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Submission #831811

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 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
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0