Submission #440802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440802	2021-07-03T07:53:05 Z	roseanne_pcy	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	244 ms	23924 KB

supertrees

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef long long ll;

#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int md = 1e9+7;
const ll inf = 1e18;
const int maxn = 1e3+5;

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

int par[maxn];

void init(int *p, int n)
{
	for(int i = 0; i< n; i++) p[i] = i;
}

int findset(int *p, int x)
{
	if(p[x] == x) return x;
	return p[x] = findset(p, p[x]);
}

void unionset(int *p, int x, int y)
{
	int a = findset(p, x);
	int b = findset(p, y);
	if(a == b) return;
	p[a] = b;
}

int construct(std::vector<std::vector<int>> p) 
{
	int n = p.size();

	init(par, n);

	bool good = true;

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			if(p[i][j] == 1)
			{
				unionset(par, i, j);
			}
			else
			{
				if(findset(par, i) == findset(par, j))
				{
					good = false;
					return 0;
				}
			}
		}
	}

	vector< vector<int> > res(n, vector<int>(n, 0));

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			res[i][j] = res[j][i] = (findset(par, i) == j);
		}
	}

	build(res);
	return 1;

}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:7: warning: variable 'good' set but not used [-Wunused-but-set-variable]
   56 |  bool good = true;
      |       ^~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	10 ms	1244 KB	Output is correct
7	Correct	244 ms	23884 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	10 ms	1244 KB	Output is correct
7	Correct	244 ms	23884 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	14 ms	1228 KB	Output is correct
13	Correct	241 ms	23924 KB	Output is correct
14	Correct	1 ms	240 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	588 KB	Output is correct
17	Correct	137 ms	10100 KB	Output is correct
18	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Too few ways to get from 0 to 1, should be 2 found 0
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	10 ms	1244 KB	Output is correct
7	Correct	244 ms	23884 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	14 ms	1228 KB	Output is correct
13	Correct	241 ms	23924 KB	Output is correct
14	Correct	1 ms	240 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	588 KB	Output is correct
17	Correct	137 ms	10100 KB	Output is correct
18	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	10 ms	1244 KB	Output is correct
7	Correct	244 ms	23884 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	14 ms	1228 KB	Output is correct
13	Correct	241 ms	23924 KB	Output is correct
14	Correct	1 ms	240 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	588 KB	Output is correct
17	Correct	137 ms	10100 KB	Output is correct
18	Incorrect	1 ms	212 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-