Submission #999234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999234	2024-06-15T08:33:27 Z	pan	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	128 ms	30036 KB

supertrees

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;

ll par[1005];
ll find(ll x) {return ((par[x]==x)?x:par[x] = find(par[x]));}
void unite(ll x, ll y){if ((x=find(x))!=(y=find(y))) par[x] = y;}

vector<ll> compress;
ll adj[1005][1005];
bool visited[1005];

void build(std::vector<std::vector<int> > b);
int construct(std::vector<std::vector<int> > p)
{
	ll n = p.size();
	vector<vector<int> > ret(n, vector<int> (n, 0));
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (p[i][j]==3) return 0;
	for (ll i=0; i<n; ++i) par[i] = i;
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (p[i][j]!=0) unite(i, j);
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (find(i)==find(j) && p[i][j]==0) return 0;
	for (ll i=0; i<n; ++i) par[i] = i;
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (p[i][j]==1) unite(i, j);
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (find(i)==find(j) && p[i][j]!=1) return 0;
	compress.clear();
	for (ll i=0; i<n; ++i) 
	{
		//show2(i, find(i));
		if (find(i)==i) compress.pb(i);
		else ret[i][find(i)] = ret[find(i)][i] = 1;
	}
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) adj[i][j] = 0;
	for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) if (p[i][j]==2) adj[find(i)][find(j)] = adj[find(j)][find(i)] = 1;
	for (ll i=0; i<n; ++i) par[i] = i;
	for (ll u: compress) for (ll u2: compress) {if (adj[u][u2]==1) unite(u, u2);}
	for (ll u: compress) for (ll u2: compress) if (u!=u2 && find(u)==find(u2) && adj[u][u2]!=1) return 0;
	fill(visited,visited+n, 0);
	for (ll u: compress)
	{
		if (visited[u]) continue;
		vector<ll> q;
		q.pb(u);
		for (ll i=0; i<q.size(); ++i)
		{
			ll now = q[i];
			for (ll u: compress) if (!visited[u] && adj[now][u]) {visited[u] = 1; q.pb(u);}
		}
		if (q.size()==2) return 0;
		if (q.size()>1)
		{
			ret[q[0]][q.back()] = ret[q.back()][q[0]] = 1;
			for (ll i=0; i<q.size()-1; ++i) ret[q[i]][q[i+1]] = ret[q[i+1]][q[i]] = 1;
		}
	}
	build(ret);
	return 1;
	
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:75:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (ll i=0; i<q.size(); ++i)
      |                ~^~~~~~~~~
supertrees.cpp:84:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for (ll i=0; i<q.size()-1; ++i) ret[q[i]][q[i+1]] = ret[q[i+1]][q[i]] = 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	344 KB	Output is correct
6	Correct	5 ms	3416 KB	Output is correct
7	Correct	121 ms	29956 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	344 KB	Output is correct
6	Correct	5 ms	3416 KB	Output is correct
7	Correct	121 ms	29956 KB	Output is correct
8	Correct	0 ms	348 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	348 KB	Output is correct
12	Correct	6 ms	3420 KB	Output is correct
13	Correct	121 ms	30036 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	62 ms	12068 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	30 ms	9956 KB	Output is correct
21	Correct	123 ms	29948 KB	Output is correct
22	Correct	118 ms	30032 KB	Output is correct
23	Correct	127 ms	30036 KB	Output is correct
24	Correct	122 ms	30036 KB	Output is correct
25	Correct	49 ms	12112 KB	Output is correct
26	Correct	47 ms	12120 KB	Output is correct
27	Correct	128 ms	29968 KB	Output is correct
28	Correct	120 ms	30036 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 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
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	b[0][0] is not 0
3	Halted	0 ms	0 KB	-

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	344 KB	Output is correct
6	Correct	5 ms	3416 KB	Output is correct
7	Correct	121 ms	29956 KB	Output is correct
8	Correct	0 ms	348 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	348 KB	Output is correct
12	Correct	6 ms	3420 KB	Output is correct
13	Correct	121 ms	30036 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	62 ms	12068 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	30 ms	9956 KB	Output is correct
21	Correct	123 ms	29948 KB	Output is correct
22	Correct	118 ms	30032 KB	Output is correct
23	Correct	127 ms	30036 KB	Output is correct
24	Correct	122 ms	30036 KB	Output is correct
25	Correct	49 ms	12112 KB	Output is correct
26	Correct	47 ms	12120 KB	Output is correct
27	Correct	128 ms	29968 KB	Output is correct
28	Correct	120 ms	30036 KB	Output is correct
29	Correct	0 ms	600 KB	Output is correct
30	Correct	0 ms	348 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	344 KB	Output is correct
6	Correct	5 ms	3416 KB	Output is correct
7	Correct	121 ms	29956 KB	Output is correct
8	Correct	0 ms	348 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	348 KB	Output is correct
12	Correct	6 ms	3420 KB	Output is correct
13	Correct	121 ms	30036 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	62 ms	12068 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	30 ms	9956 KB	Output is correct
21	Correct	123 ms	29948 KB	Output is correct
22	Correct	118 ms	30032 KB	Output is correct
23	Correct	127 ms	30036 KB	Output is correct
24	Correct	122 ms	30036 KB	Output is correct
25	Correct	49 ms	12112 KB	Output is correct
26	Correct	47 ms	12120 KB	Output is correct
27	Correct	128 ms	29968 KB	Output is correct
28	Correct	120 ms	30036 KB	Output is correct
29	Correct	0 ms	600 KB	Output is correct
30	Correct	0 ms	348 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 #999234

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