Submission #977266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977266	2024-05-07T15:23:05 Z	thegamercoder19	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	176 ms	30048 KB

supertrees

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

#define M_PI       3.14159265358979323846
#define FILER 0
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = pow(10, 9) + 7;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const ull INFUL = 0x3f3f3f3f3f3f3f3f;
const ll INFT = 0x3f3f3f3f;
const ull MAX = 1LL << 24;
const ll MODD = 998244353;
const double EPS = 1e-10;
#define V vector
#define pll pair<ll, ll>
#define pull2 pair<ull,ull>
#define MS multiset
#define M map
#define Q queue
#define PQ priority_queue
#define IOF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
#define FORR(typ,i,a,b,c) for(typ i = a; i > b; i -= c)
#define FORA(a,i) for(auto &i : a)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define sorta(a) sort(all(a))
#define sortd(a) sort(all(a), greater<ll>())
#define setp(x) setprecision(x)<<fixed
#define RET return
#define log(a,b) log(b)/log(a)
#define WH(s) while(s)
#define WHI(t) WH(t--)
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define YESNO(s) cout << (s ? "YES" : "NO") << endl;
#define YesNo(s) cout<<(s?"Yes":"No")<<endl;
#define TYP 0
using namespace std;

V<ll> comp;
V<bool> us;
V<V<int>> g;

ll n;
void dfs(ll u)
{
	us[u] = 1;
	FOR(ll, v, 0, n, 1)
		if (g[u][v] && !us[v])dfs(v);
	comp.push_back(u);
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size(); us.resize(n);
	g.resize(n, V<int>(n));
	FOR(ll, i, 0, n, 1)
		FOR(ll, j, i + 1, n, 1)
		if (p[i][j])g[i][j] = g[j][i] = 1;
	V<V<int>> p1(n, V<int>(n)), g1(n, V<int>(n));
	FOR(ll,i,0,n,1)
		if (!us[i])
		{
			comp.clear();
			dfs(i);
			FOR(ll, j, 0, comp.size() - 1, 1) g1[comp[j]][comp[j + 1]] = g1[comp[j + 1]][comp[j]] = 1;
			FORA(comp, u)
				FORA(comp, v)
				p1[u][v] = p1[v][u] = 1;
		}
	FOR(ll, i, 0, n, 1)
		FOR(ll, j, 0, n, 1) if (p1[i][j] != p[i][j])RET 0;
	build(g1);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:24:43: 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]
   24 | #define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
......
   70 |    FOR(ll, j, 0, comp.size() - 1, 1) g1[comp[j]][comp[j + 1]] = g1[comp[j + 1]][comp[j]] = 1;
      |            ~~~~~~~~~~~~~~~~~~~~~           
supertrees.cpp:70:4: note: in expansion of macro 'FOR'
   70 |    FOR(ll, j, 0, comp.size() - 1, 1) g1[comp[j]][comp[j + 1]] = g1[comp[j + 1]][comp[j]] = 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	1612 KB	Output is correct
7	Correct	161 ms	30048 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	1612 KB	Output is correct
7	Correct	161 ms	30048 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	7 ms	1628 KB	Output is correct
13	Correct	163 ms	29960 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	3 ms	1116 KB	Output is correct
17	Correct	81 ms	19996 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	43 ms	7764 KB	Output is correct
21	Correct	159 ms	29968 KB	Output is correct
22	Correct	166 ms	30032 KB	Output is correct
23	Correct	161 ms	29900 KB	Output is correct
24	Correct	160 ms	29956 KB	Output is correct
25	Correct	71 ms	19972 KB	Output is correct
26	Correct	71 ms	19984 KB	Output is correct
27	Correct	176 ms	29884 KB	Output is correct
28	Correct	156 ms	30020 KB	Output is correct

Subtask #3
0 / 19.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	1 ms	500 KB	Output is correct
5	Incorrect	0 ms	348 KB	Answer gives possible 0 while actual possible 1
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	344 KB	Answer gives possible 0 while actual possible 1
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	1612 KB	Output is correct
7	Correct	161 ms	30048 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	7 ms	1628 KB	Output is correct
13	Correct	163 ms	29960 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	3 ms	1116 KB	Output is correct
17	Correct	81 ms	19996 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	43 ms	7764 KB	Output is correct
21	Correct	159 ms	29968 KB	Output is correct
22	Correct	166 ms	30032 KB	Output is correct
23	Correct	161 ms	29900 KB	Output is correct
24	Correct	160 ms	29956 KB	Output is correct
25	Correct	71 ms	19972 KB	Output is correct
26	Correct	71 ms	19984 KB	Output is correct
27	Correct	176 ms	29884 KB	Output is correct
28	Correct	156 ms	30020 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Correct	1 ms	500 KB	Output is correct
33	Incorrect	0 ms	348 KB	Answer gives possible 0 while actual possible 1
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	1612 KB	Output is correct
7	Correct	161 ms	30048 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	7 ms	1628 KB	Output is correct
13	Correct	163 ms	29960 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	3 ms	1116 KB	Output is correct
17	Correct	81 ms	19996 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	43 ms	7764 KB	Output is correct
21	Correct	159 ms	29968 KB	Output is correct
22	Correct	166 ms	30032 KB	Output is correct
23	Correct	161 ms	29900 KB	Output is correct
24	Correct	160 ms	29956 KB	Output is correct
25	Correct	71 ms	19972 KB	Output is correct
26	Correct	71 ms	19984 KB	Output is correct
27	Correct	176 ms	29884 KB	Output is correct
28	Correct	156 ms	30020 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Correct	1 ms	500 KB	Output is correct
33	Incorrect	0 ms	348 KB	Answer gives possible 0 while actual possible 1
34	Halted	0 ms	0 KB	-

Submission #977266

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