Submission #899402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899402	2024-01-06T03:22:50 Z	oblantis	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	161 ms	26420 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18;
const int mod = 1e9+7;
const int maxn = 1000 + 2;
vector<int> g[maxn];
int x;
int h[maxn], oh[maxn], used[maxn];
bool two[maxn], three[maxn];
bool was[maxn];
void dfs(int v){
	h[v] = x;
	was[v] = 1;
	for(auto i : g[v]){
		if(!was[i]){
			dfs(i);
		}
	}
}
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n);
	for(int i = 0; i < n; i++)ans[i].resize(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			if(i == j){
				if(p[i][i] != 1)return 0;
				continue;
			}
			if(p[i][j]){
				g[j].pb(i);
				g[i].pb(j);
			}
			if(p[i][j] != p[j][i]){
				return 0;
			}
		}
	}
	for(int i = 0; i < n; i++){
		if(!was[i]){
			x = i;
			dfs(i);
		}
	}
	for(int i = 0; i < n; i++){
		oh[i] = used[i] = -1;
		for(int j = 0; j < n; j++){
			if(h[i] == h[j] && p[i][j] == 0){
				return 0;
			}
			if(h[i] == h[j]){
				if(p[i][j] == 2){
					two[h[i]] = 1;
				}
				else if(p[i][j] == 3){
					three[h[i]] = 1;
				}
				if(two[h[i]] && three[h[i]]){
					return 0;
				}
			}
		}
	}
	vt<int> unq;
	for(int i = 0; i < n; i++){
		if(oh[i] == -1){
			unq.pb(i);
			oh[i] = i;
			for(auto j : g[i]){
				if(p[i][j] == 1){
					if(oh[j] != -1){
						return 0;
					}
					oh[j] = i;
					ans[i][j] = ans[j][i] = 1;
				}
			}
		}
	}
	int sz = unq.size();
	for(int I = 0; I < sz; I++){
		int i = unq[I];
		if(used[i] != -1)continue;
		used[i] = i;
		if(h[i] != i)return 0;
		if(!three[i] && !two[i])continue;
		bool wt = 0;
		if(three[i])wt = 1;
		int o = -1, ls = -1, z = -1;
		for(int J = 0; J < sz; J++){
			int j = unq[J];
			if(p[i][j] > 1 && used[j] == -1){
				used[j] = i;
				if(o == -1){
					o = j;
					ans[i][o] = ans[o][i] = 1;
				}
				else {
					if(ls == -1)ls = j;
					ans[z][j] = ans[j][z] = 1;
					z = j;
				}
			}
			else if(p[i][j] > 1)return 0;
		}
		if(z == -1)return 0;
		ans[o][z] = ans[z][o] = 1;
		if(wt && z == ls){
			return 0;
		}
		else if(wt){
			ans[z][i] = ans[i][z] = 1;
		}
	}
	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	7 ms	1372 KB	Output is correct
7	Correct	159 ms	26420 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	7 ms	1372 KB	Output is correct
7	Correct	159 ms	26420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	151 ms	21988 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	71 ms	14884 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	38 ms	5972 KB	Output is correct
21	Correct	161 ms	22952 KB	Output is correct
22	Correct	150 ms	22012 KB	Output is correct
23	Correct	157 ms	24148 KB	Output is correct
24	Correct	156 ms	22100 KB	Output is correct
25	Correct	66 ms	12836 KB	Output is correct
26	Correct	67 ms	12112 KB	Output is correct
27	Correct	161 ms	25380 KB	Output is correct
28	Correct	155 ms	22096 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Runtime error	1 ms	604 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Runtime error	604 KB	Execution killed with signal 11
3	Halted	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	7 ms	1372 KB	Output is correct
7	Correct	159 ms	26420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	151 ms	21988 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	71 ms	14884 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	38 ms	5972 KB	Output is correct
21	Correct	161 ms	22952 KB	Output is correct
22	Correct	150 ms	22012 KB	Output is correct
23	Correct	157 ms	24148 KB	Output is correct
24	Correct	156 ms	22100 KB	Output is correct
25	Correct	66 ms	12836 KB	Output is correct
26	Correct	67 ms	12112 KB	Output is correct
27	Correct	161 ms	25380 KB	Output is correct
28	Correct	155 ms	22096 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Runtime error	1 ms	604 KB	Execution killed with signal 11
34	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	7 ms	1372 KB	Output is correct
7	Correct	159 ms	26420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	151 ms	21988 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	71 ms	14884 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	38 ms	5972 KB	Output is correct
21	Correct	161 ms	22952 KB	Output is correct
22	Correct	150 ms	22012 KB	Output is correct
23	Correct	157 ms	24148 KB	Output is correct
24	Correct	156 ms	22100 KB	Output is correct
25	Correct	66 ms	12836 KB	Output is correct
26	Correct	67 ms	12112 KB	Output is correct
27	Correct	161 ms	25380 KB	Output is correct
28	Correct	155 ms	22096 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Runtime error	1 ms	604 KB	Execution killed with signal 11
34	Halted	0 ms	0 KB	-

Submission #899402

Compilation message

Subtask #1 11.0 / 11.0

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

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0