Submission #1080121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1080121	2024-08-29T07:17:21 Z	GrindMachine	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	166 ms	23628 KB

supertrees

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; ++i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char* s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "supertrees.h"

vector<int> par(N);

void create(int n){
	rep(i,n) par[i] = i;
}

int find(int u){
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}

void merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;
	par[v] = u;
}

int construct(std::vector<std::vector<int>> a) {
	int n = a.size();
	vector<vector<int>> ans(n,vector<int>(n));
	create(n);

	rep(i,n){
		rep(j,n){
			if(a[i][j]){
				merge(i,j);
			}
		}
	}

	rep(i,n){
		rep(j,n){
			int x = a[i][j] > 0;
			int y = find(i) == find(j);
			if(x != y){
				return 0;
			}
		}
	}

	vector<int> group[n];
	rep(i,n) group[find(i)].pb(i);

	auto f = [&](int u, int v){
		ans[u][v] = ans[v][u] = 1;
	};

	rep(c,n){
		auto &nodes = group[c];
		if(nodes.empty()) conts;
		create(n);
		vector<int> cc[n];
		int m = sz(nodes);

		rep(i,m){
			rep(j,i){
				int u = nodes[i], v = nodes[j];
				if(a[u][v] == 1){
					merge(u,v);
				}
			}
		}

		rep(i,m){
			rep(j,i){
				int u = nodes[i], v = nodes[j];
				int x = a[u][v] == 1;
				int y = find(u) == find(v);
				if(x != y){
					return 0;
				}
			}
		}

		trav(u,nodes){
			cc[find(u)].pb(u);
		}

		vector<int> cyc;

		rep(id,n){
			if(cc[id].empty()) conts;
			auto &curr = cc[id];
			cyc.pb(curr[0]);
			rep(i,sz(curr)-1){
				f(curr[i],curr[i+1]);
			}
		}

		int siz = sz(cyc);
		// if(siz <= 2) return 0;

		if(siz > 1){
			rep(i,siz){
				f(cyc[i],cyc[(i+1)%siz]);
			}
		}
	}

	build(ans);
	return 1;

	// std::vector<std::vector<int>> answer;
	// for (int i = 0; i < n; i++) {
	// 	std::vector<int> row;
	// 	row.resize(n);
	// 	answer.push_back(row);
	// }
	// build(answer);
	// 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	1 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	6 ms	1176 KB	Output is correct
7	Correct	128 ms	23420 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	1 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	6 ms	1176 KB	Output is correct
7	Correct	128 ms	23420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1368 KB	Output is correct
13	Correct	118 ms	23492 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	3 ms	960 KB	Output is correct
17	Correct	61 ms	13392 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	444 KB	Output is correct
20	Correct	32 ms	6224 KB	Output is correct
21	Correct	124 ms	23332 KB	Output is correct
22	Correct	138 ms	23272 KB	Output is correct
23	Correct	166 ms	23388 KB	Output is correct
24	Correct	121 ms	23444 KB	Output is correct
25	Correct	53 ms	13476 KB	Output is correct
26	Correct	51 ms	13392 KB	Output is correct
27	Correct	131 ms	23336 KB	Output is correct
28	Correct	138 ms	23380 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	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	33 ms	6264 KB	Output is correct
5	Correct	120 ms	23380 KB	Output is correct
6	Correct	119 ms	23380 KB	Output is correct
7	Correct	158 ms	23368 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	31 ms	6236 KB	Output is correct
10	Correct	121 ms	23496 KB	Output is correct
11	Correct	135 ms	23288 KB	Output is correct
12	Correct	162 ms	23364 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	440 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	36 ms	6392 KB	Output is correct
17	Correct	154 ms	23376 KB	Output is correct
18	Correct	165 ms	23628 KB	Output is correct
19	Correct	118 ms	23320 KB	Output is correct
20	Correct	138 ms	23368 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	1 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	6 ms	1176 KB	Output is correct
7	Correct	128 ms	23420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1368 KB	Output is correct
13	Correct	118 ms	23492 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	3 ms	960 KB	Output is correct
17	Correct	61 ms	13392 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	444 KB	Output is correct
20	Correct	32 ms	6224 KB	Output is correct
21	Correct	124 ms	23332 KB	Output is correct
22	Correct	138 ms	23272 KB	Output is correct
23	Correct	166 ms	23388 KB	Output is correct
24	Correct	121 ms	23444 KB	Output is correct
25	Correct	53 ms	13476 KB	Output is correct
26	Correct	51 ms	13392 KB	Output is correct
27	Correct	131 ms	23336 KB	Output is correct
28	Correct	138 ms	23380 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	1 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	6 ms	1176 KB	Output is correct
7	Correct	128 ms	23420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	5 ms	1368 KB	Output is correct
13	Correct	118 ms	23492 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	3 ms	960 KB	Output is correct
17	Correct	61 ms	13392 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	444 KB	Output is correct
20	Correct	32 ms	6224 KB	Output is correct
21	Correct	124 ms	23332 KB	Output is correct
22	Correct	138 ms	23272 KB	Output is correct
23	Correct	166 ms	23388 KB	Output is correct
24	Correct	121 ms	23444 KB	Output is correct
25	Correct	53 ms	13476 KB	Output is correct
26	Correct	51 ms	13392 KB	Output is correct
27	Correct	131 ms	23336 KB	Output is correct
28	Correct	138 ms	23380 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 #1080121

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