oj.uz

Submission #813008

# Submission time Handle Problem Language Result Execution time Memory
813008 2023-08-07T12:40:12 Z OrazB Connecting Supertrees (IOI20_supertrees) C++14
56 / 100
 391 ms 27280 KB 
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 1e3+5;
int T, vis[N][N], cur[N], tp[N];
set<int> A[N], B[N];

int F1(int n, int i, vector<vector<int>> p, vector<vector<int>>&b){
	if (A[cur[i]].find(i) != A[cur[i]].end()) return p[tp[i]] == p[i];
	for (int j = 0; j < n; j++){
		if (i == j) continue;
		if (vis[cur[i]][j] != (p[i][j] == 0)) return 0;
		if (p[i][j] == 1){
			tp[j] = i;
			A[cur[i]].insert(j);
			B[cur[i]].erase(j);
			b[i][j] = b[j][i] = 1;
		}
	}
	return 1;
}

void F2(int n, int i, vector<vector<int>> p, vector<vector<int>>&b){
	++T;
	B[T].insert(i);
	for (int j = 0; j < n; j++){
		if (i == j) continue;
		if (p[i][j] == 0) vis[T][j] = 1;
		else{
			cur[j] = T;
			if (p[i][j] == 1){
				tp[j] = i;
				A[T].insert(j);
				b[i][j] = b[j][i] = 1;
			}else B[T].insert(j);
		}
	}
}

// void build(vector<vector<int>> p){
// 	int n = p.size();
// 	for (int i = 0; i < n; i++){
// 		for (int j = 0; j < n; j++) cout << p[i][j] << " ";
// 		cout << '\n';
// 	}
// }

int construct(vector<vector<int>> p){
	int n = p.size();
	vector<vector<int>> b(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++){
		if (count(all(p[i]), 3)) return 0; 
		if (cur[i]){
			if (!F1(n, i, p, b)) return 0;
		}else F2(n, i, p, b);
	}
	for (int i = 1; i <= T; i++){
		if (B[i].size() <= 1) continue;
		int lst = *B[i].rbegin();
		for (auto j : B[i]){
			b[lst][j] = b[j][lst] = 1;
			lst = j;
		}
	}
	build(b);
	return 1;

}

// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n;
// 	cin >> n;
// 	vector<vector<int>> p(n, vector<int>(n));
// 	for (int i = 0; i < n; i++){
// 		for (int j = 0; j < n; j++) cin >> p[i][j];
// 	}
// 	cout << construct(p);
// }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 329 ms 23284 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 329 ms 23284 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 9 ms 2108 KB Output is correct
13 Correct 368 ms 27280 KB Output is correct
14 Correct 0 ms 396 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 111 ms 17376 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 70 ms 6576 KB Output is correct
21 Correct 379 ms 23296 KB Output is correct
22 Correct 341 ms 24924 KB Output is correct
23 Correct 342 ms 23368 KB Output is correct
24 Correct 383 ms 27052 KB Output is correct
25 Correct 232 ms 17436 KB Output is correct
26 Correct 187 ms 18400 KB Output is correct
27 Correct 391 ms 23296 KB Output is correct
28 Correct 371 ms 27044 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 70 ms 6640 KB Output is correct
5 Correct 341 ms 23332 KB Output is correct
6 Correct 378 ms 24856 KB Output is correct
7 Correct 339 ms 23368 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 68 ms 6640 KB Output is correct
10 Correct 376 ms 23448 KB Output is correct
11 Correct 348 ms 24160 KB Output is correct
12 Correct 361 ms 23292 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 68 ms 6676 KB Output is correct
17 Correct 334 ms 23396 KB Output is correct
18 Correct 344 ms 23276 KB Output is correct
19 Correct 340 ms 23288 KB Output is correct
20 Correct 351 ms 26972 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 329 ms 23284 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 9 ms 2108 KB Output is correct
13 Correct 368 ms 27280 KB Output is correct
14 Correct 0 ms 396 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 111 ms 17376 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 70 ms 6576 KB Output is correct
21 Correct 379 ms 23296 KB Output is correct
22 Correct 341 ms 24924 KB Output is correct
23 Correct 342 ms 23368 KB Output is correct
24 Correct 383 ms 27052 KB Output is correct
25 Correct 232 ms 17436 KB Output is correct
26 Correct 187 ms 18400 KB Output is correct
27 Correct 391 ms 23296 KB Output is correct
28 Correct 371 ms 27044 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 329 ms 23284 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 9 ms 2108 KB Output is correct
13 Correct 368 ms 27280 KB Output is correct
14 Correct 0 ms 396 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 111 ms 17376 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 70 ms 6576 KB Output is correct
21 Correct 379 ms 23296 KB Output is correct
22 Correct 341 ms 24924 KB Output is correct
23 Correct 342 ms 23368 KB Output is correct
24 Correct 383 ms 27052 KB Output is correct
25 Correct 232 ms 17436 KB Output is correct
26 Correct 187 ms 18400 KB Output is correct
27 Correct 391 ms 23296 KB Output is correct
28 Correct 371 ms 27044 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Incorrect 0 ms 340 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -