Submission #1034248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1034248	2024-07-25T11:17:30 Z	Gray	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	150 ms	26196 KB

supertrees

#include "supertrees.h"
#include <cassert>
#include <map>
#include <vector>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
 
struct DSU{
	vector<int> p;
	int n, cnt;
	DSU(int N){
		n=N;
		cnt=n;
		p.resize(n, -1);
	}
	int get(int x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	bool unite(int a, int b){
		a=get(a);
		b=get(b);
		if (a==b) return 0;
		cnt--;
		if (a<b) swap(a, b);
		p[a]=b;
		return 1;
	}
};
 
int construct(std::vector<std::vector<int>> p) {
	int n = (int)p.size();
	DSU tr(n), tr2(n);
	vector<vector<int>> A(n);
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i!=j and p[i][j]){
				tr.unite(i, j);
				if (p[i][j]==1) tr2.unite(i, j);
			}
		}
	}
	map<int, vector<int>> ccs;
	for (int i=0; i<n; i++){
		// assert(tr.get(i)<tr.cnt);
		ccs[tr.get(i)].push_back(i);
	}
	vector<vector<int>> ans(n, vector<int>(n));
	vector<vector<int>> shadow(n, vector<int>(n));
	for (auto &[_, arr]:ccs){
		map<int, vector<int>> groups;
		for (auto ch:arr){
			groups[tr2.get(ch)].push_back(ch);
		}
		for (ll j=0; j<(int)(arr.size()); j++){
			for (ll k=j+1; k<(int)(arr.size()); k++){
				shadow[arr[j]][arr[k]]=shadow[arr[k]][arr[j]]=2;
			}
		}
		vector<int> circle;
		for (auto &[icc,mem]:groups){
			for (ll j=1; j<(int)mem.size(); j++){
				ans[mem[j]][mem[j-1]]=ans[mem[j-1]][mem[j]]=1;
			}
			for (ll j=0; j<(int)mem.size(); j++){
				for (ll k=j+1; k<(int)mem.size(); k++){
					shadow[mem[j]][mem[k]]=shadow[mem[k]][mem[j]]=1;
				}
			}
			circle.push_back(mem[0]);
		}
		if (circle.size()==1) continue;
		for (ll j=0; j<(int)circle.size(); j++){
			int nxt = (j+1)%(int)(circle.size());
			ans[circle[j]][circle[nxt]]=ans[circle[nxt]][circle[j]]=1;
		}
	}
	for (ll i=0; i<n; i++){
		for (ll j=0; j<n; j++){
			if ((i!=j and p[i][j]!=shadow[i][j]) or p[i][j]==3){
				return 0;
			}
		}
	}
	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	5 ms	1372 KB	Output is correct
7	Correct	134 ms	25940 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	5 ms	1372 KB	Output is correct
7	Correct	134 ms	25940 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	1372 KB	Output is correct
13	Correct	112 ms	26140 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	66 ms	16120 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	6788 KB	Output is correct
21	Correct	120 ms	26144 KB	Output is correct
22	Correct	125 ms	26192 KB	Output is correct
23	Correct	127 ms	25936 KB	Output is correct
24	Correct	111 ms	26116 KB	Output is correct
25	Correct	53 ms	16208 KB	Output is correct
26	Correct	64 ms	16208 KB	Output is correct
27	Correct	150 ms	25940 KB	Output is correct
28	Correct	116 ms	26196 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Incorrect	348 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	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	29 ms	6744 KB	Output is correct
5	Correct	109 ms	26192 KB	Output is correct
6	Correct	123 ms	26008 KB	Output is correct
7	Correct	132 ms	25940 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	30 ms	6736 KB	Output is correct
10	Correct	124 ms	26104 KB	Output is correct
11	Correct	116 ms	25940 KB	Output is correct
12	Correct	137 ms	25940 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	28 ms	6744 KB	Output is correct
17	Correct	113 ms	26124 KB	Output is correct
18	Correct	133 ms	25936 KB	Output is correct
19	Correct	119 ms	25940 KB	Output is correct
20	Correct	113 ms	26028 KB	Output is correct

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	5 ms	1372 KB	Output is correct
7	Correct	134 ms	25940 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	1372 KB	Output is correct
13	Correct	112 ms	26140 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	66 ms	16120 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	6788 KB	Output is correct
21	Correct	120 ms	26144 KB	Output is correct
22	Correct	125 ms	26192 KB	Output is correct
23	Correct	127 ms	25936 KB	Output is correct
24	Correct	111 ms	26116 KB	Output is correct
25	Correct	53 ms	16208 KB	Output is correct
26	Correct	64 ms	16208 KB	Output is correct
27	Correct	150 ms	25940 KB	Output is correct
28	Correct	116 ms	26196 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Incorrect	0 ms	348 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	0 ms	348 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	5 ms	1372 KB	Output is correct
7	Correct	134 ms	25940 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	1372 KB	Output is correct
13	Correct	112 ms	26140 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	66 ms	16120 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	6788 KB	Output is correct
21	Correct	120 ms	26144 KB	Output is correct
22	Correct	125 ms	26192 KB	Output is correct
23	Correct	127 ms	25936 KB	Output is correct
24	Correct	111 ms	26116 KB	Output is correct
25	Correct	53 ms	16208 KB	Output is correct
26	Correct	64 ms	16208 KB	Output is correct
27	Correct	150 ms	25940 KB	Output is correct
28	Correct	116 ms	26196 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Submission #1034248

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