oj.uz

Submission #757724

# Submission time Handle Problem Language Result Execution time Memory
757724 2023-06-13T16:18:39 Z Piokemon Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 226 ms 24012 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

bool odw[1009];
int nr[1009];

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<int> czesc(n,0);
	vector<vector<int>> answer(n,czesc);
	for(int i=0;i<=n;i++) odw[i]=0;
	for (int i=0;i<n;i++){
		if (odw[i]) continue;
		nr[i] = i;
		odw[i] = 1;
		for (int j=0;j<n;j++){
			if (p[i][j]==3) return 0;
			if (odw[j] || i==j) continue;
			if (p[i][j]==1){
				answer[i][j] = 1;
				answer[j][i] = 1;
				nr[j] = i;
				odw[j] = 1;
			}
		}
	}
	for(int i=0;i<=n;i++) odw[i]=0;
	/*cout << "nr: ";
	for (int i=0;i<n;i++) cout << nr[i] << ' ';
	cout << '\n';*/
	for (int i=0;i<n;i++){
		if (nr[i]!=i || odw[i]) continue;
		vector<int> cykl;
		cykl.push_back(i);
		for (int j=0;j<n;j++){
			if (p[i][j]==2 && !odw[nr[j]]){
				cykl.push_back(nr[j]);
				odw[nr[j]] = 1;
			}
		}
		/*cout << "cykl: ";
		for (int j:cykl){
			cout << j << ' ';
		}
		cout << '\n';*/
		if (cykl.size()==1) continue;
		for (int j=0;j<cykl.size()-1;j++){
			answer[cykl[j]][cykl[j+1]] = 1;
			answer[cykl[j+1]][cykl[j]] = 1;
		}
		answer[cykl.back()][cykl[0]] = 1;
		answer[cykl[0]][cykl.back()] =1;
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int j=0;j<cykl.size()-1;j++){
      |                ~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1208 KB Output is correct
7 Correct 188 ms 23928 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1208 KB Output is correct
7 Correct 188 ms 23928 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 182 ms 23924 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 47 ms 6232 KB Output is correct
5 Correct 170 ms 23928 KB Output is correct
6 Correct 186 ms 23932 KB Output is correct
7 Correct 226 ms 24012 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 54 ms 6252 KB Output is correct
10 Correct 195 ms 23972 KB Output is correct
11 Correct 202 ms 24012 KB Output is correct
12 Correct 186 ms 24012 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 46 ms 6260 KB Output is correct
17 Correct 176 ms 23992 KB Output is correct
18 Correct 187 ms 23936 KB Output is correct
19 Correct 177 ms 23940 KB Output is correct
20 Correct 192 ms 24012 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1208 KB Output is correct
7 Correct 188 ms 23928 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 182 ms 23924 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 1208 KB Output is correct
7 Correct 188 ms 23928 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 182 ms 23924 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -