Submission #831879

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831879	2023-08-20T16:39:57 Z	gesgha	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	167 ms	22072 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 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); i++) {
			for (int j = 0; j < sz(ids); 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]) {
					if (cnt[x][1] != sz(palki[i])) return 0;
					if (cnt[x][0] != n - sz(ids)) return 0;
					if (cnt[x][2] != sz(ids) - sz(palki[i]))return 0;
					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;
			// for (int i = 0; i < sz(ids); i++) {
			// 	for (int j = 0; j < sz(ids); j++) {
			// 		if (!p[i][j]) return 0;
			// 	}
			// }
		} 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	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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	10 ms	1108 KB	Output is correct
7	Correct	151 ms	21984 KB	Output is correct

Subtask #2
10.0 / 10.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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	10 ms	1108 KB	Output is correct
7	Correct	151 ms	21984 KB	Output is correct
8	Correct	1 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	1204 KB	Output is correct
13	Correct	150 ms	22020 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	65 ms	12052 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	149 ms	21964 KB	Output is correct
22	Correct	148 ms	22028 KB	Output is correct
23	Correct	158 ms	22064 KB	Output is correct
24	Correct	150 ms	22036 KB	Output is correct
25	Correct	60 ms	12052 KB	Output is correct
26	Correct	60 ms	12108 KB	Output is correct
27	Correct	152 ms	22036 KB	Output is correct
28	Correct	167 ms	22072 KB	Output is correct

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	39 ms	5764 KB	Output is correct
5	Correct	150 ms	22020 KB	Output is correct
6	Correct	150 ms	22044 KB	Output is correct
7	Correct	154 ms	22024 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	38 ms	5768 KB	Output is correct
10	Correct	157 ms	22036 KB	Output is correct
11	Correct	153 ms	21964 KB	Output is correct
12	Correct	158 ms	22024 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	45 ms	5676 KB	Output is correct
17	Correct	151 ms	21992 KB	Output is correct
18	Correct	151 ms	21964 KB	Output is correct
19	Correct	151 ms	22024 KB	Output is correct
20	Correct	153 ms	22020 KB	Output is correct

Subtask #5
0 / 21.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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	10 ms	1108 KB	Output is correct
7	Correct	151 ms	21984 KB	Output is correct
8	Correct	1 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	1204 KB	Output is correct
13	Correct	150 ms	22020 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	65 ms	12052 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	149 ms	21964 KB	Output is correct
22	Correct	148 ms	22028 KB	Output is correct
23	Correct	158 ms	22064 KB	Output is correct
24	Correct	150 ms	22036 KB	Output is correct
25	Correct	60 ms	12052 KB	Output is correct
26	Correct	60 ms	12108 KB	Output is correct
27	Correct	152 ms	22036 KB	Output is correct
28	Correct	167 ms	22072 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Incorrect	0 ms	212 KB	Answer gives possible 1 while actual possible 0
33	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	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	10 ms	1108 KB	Output is correct
7	Correct	151 ms	21984 KB	Output is correct
8	Correct	1 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	1204 KB	Output is correct
13	Correct	150 ms	22020 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	65 ms	12052 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	149 ms	21964 KB	Output is correct
22	Correct	148 ms	22028 KB	Output is correct
23	Correct	158 ms	22064 KB	Output is correct
24	Correct	150 ms	22036 KB	Output is correct
25	Correct	60 ms	12052 KB	Output is correct
26	Correct	60 ms	12108 KB	Output is correct
27	Correct	152 ms	22036 KB	Output is correct
28	Correct	167 ms	22072 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Incorrect	0 ms	212 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Submission #831879

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.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
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0