답안 #831808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831808	2023-08-20T15:35:31 Z	gesgha	슈퍼트리 잇기 (IOI20_supertrees)	C++17	11 / 100	1000 ms	24136 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);
		}
		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) - 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	12 ms	1180 KB	Output is correct
7	Correct	796 ms	23928 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	12 ms	1180 KB	Output is correct
7	Correct	796 ms	23928 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	296 KB	Output is correct
12	Correct	7 ms	1236 KB	Output is correct
13	Correct	161 ms	23924 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	304 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	75 ms	14076 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	41 ms	6204 KB	Output is correct
21	Correct	181 ms	24012 KB	Output is correct
22	Correct	167 ms	24136 KB	Output is correct
23	Correct	334 ms	23904 KB	Output is correct
24	Correct	161 ms	24012 KB	Output is correct
25	Incorrect	172 ms	23936 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	결과	메모리	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
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	300 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	41 ms	6240 KB	Output is correct
5	Correct	172 ms	23928 KB	Output is correct
6	Correct	182 ms	23956 KB	Output is correct
7	Correct	333 ms	23940 KB	Output is correct
8	Correct	0 ms	292 KB	Output is correct
9	Correct	51 ms	6204 KB	Output is correct
10	Correct	431 ms	24036 KB	Output is correct
11	Correct	171 ms	23940 KB	Output is correct
12	Execution timed out	1078 ms	14068 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	12 ms	1180 KB	Output is correct
7	Correct	796 ms	23928 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	296 KB	Output is correct
12	Correct	7 ms	1236 KB	Output is correct
13	Correct	161 ms	23924 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	304 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	75 ms	14076 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	41 ms	6204 KB	Output is correct
21	Correct	181 ms	24012 KB	Output is correct
22	Correct	167 ms	24136 KB	Output is correct
23	Correct	334 ms	23904 KB	Output is correct
24	Correct	161 ms	24012 KB	Output is correct
25	Incorrect	172 ms	23936 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	0 ms	304 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	12 ms	1180 KB	Output is correct
7	Correct	796 ms	23928 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	0 ms	296 KB	Output is correct
11	Correct	0 ms	296 KB	Output is correct
12	Correct	7 ms	1236 KB	Output is correct
13	Correct	161 ms	23924 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	304 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	75 ms	14076 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	41 ms	6204 KB	Output is correct
21	Correct	181 ms	24012 KB	Output is correct
22	Correct	167 ms	24136 KB	Output is correct
23	Correct	334 ms	23904 KB	Output is correct
24	Correct	161 ms	24012 KB	Output is correct
25	Incorrect	172 ms	23936 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

답안 #831808

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