oj.uz

Submission #534638

# Submission time Handle Problem Language Result Execution time Memory
534638 2022-03-08T12:25:20 Z shrimb Carnival (CEOI14_carnival) C++17
20 / 100
 135 ms 468 KB 
#include"bits/stdc++.h"
#define int long long
// #define endl '\n'
using namespace std;

int dsu[20001];
int ans[20001];

int Find (int x) {
	return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
	dsu[Find(a)] = Find(b);
}

int asked[151][151];
bool Query (int a, int b) {
	if (asked[a][b] != -1) return asked[a][b];
	if (Find(a) == Find(b)) return asked[a][b] = asked[b][a] = 1;
	cout << "2 " << a << " " << b << endl;
	int x;
	cin >> x;
	return asked[a][b] = asked[b][a] = (x == 1);
}
bitset<151> vis;


signed main () {
	srand(time(0));
	memset(asked, -1, sizeof asked);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i++) dsu[i] = i;
	for (int i = 1 ; i <= n ; i++) {
		vis = 0;
		vis[i] = 1;
		int a[n];
		for (int j = 0 ; j < n ; j++) a[j] = j + 1;
		random_shuffle(a, a + n);
		for (int j = 0; j < n ; j++) {
			int x = a[j];
			if (vis[x]) {continue;}
			else {
				vis[x] = 1;
				if (Query(i, x)) Union(i, x);
			}
		}
	}

	int c = 1;
	for (int i = 1 ; i <= n ; i++) if (dsu[i] == i) ans[i] = c++;
	cout << 0 << " ";
	for (int i = 1 ; i <= n ; i++) cout << ans[Find(i)] << " ";
	cout << endl;
}

Compilation message

carnival.cpp: In function 'bool Query(long long int, long long int)':
carnival.cpp:20:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   20 |  if (Find(a) == Find(b)) return asked[a][b] = asked[b][a] = 1;
      |                                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
carnival.cpp:24:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |  return asked[a][b] = asked[b][a] = (x == 1);
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 66 ms 456 KB Partially correct
2 Partially correct 59 ms 460 KB Partially correct
3 Partially correct 73 ms 456 KB Partially correct
4 Partially correct 77 ms 456 KB Partially correct
5 Partially correct 49 ms 464 KB Partially correct
6 Correct 4 ms 456 KB Output is correct
7 Partially correct 70 ms 464 KB Partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 79 ms 460 KB Partially correct
2 Partially correct 135 ms 464 KB Partially correct
3 Partially correct 54 ms 460 KB Partially correct
4 Partially correct 67 ms 456 KB Partially correct
5 Partially correct 57 ms 460 KB Partially correct
6 Correct 23 ms 468 KB Output is correct
7 Partially correct 85 ms 464 KB Partially correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 456 KB Output is correct
2 Partially correct 87 ms 460 KB Partially correct
3 Partially correct 93 ms 460 KB Partially correct
4 Partially correct 114 ms 460 KB Partially correct
5 Partially correct 72 ms 460 KB Partially correct
6 Partially correct 44 ms 464 KB Partially correct
7 Partially correct 80 ms 456 KB Partially correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 65 ms 460 KB Partially correct
2 Partially correct 81 ms 460 KB Partially correct
3 Partially correct 105 ms 460 KB Partially correct
4 Partially correct 111 ms 464 KB Partially correct
5 Partially correct 60 ms 456 KB Partially correct
6 Partially correct 87 ms 456 KB Partially correct
7 Partially correct 106 ms 460 KB Partially correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 464 KB Partially correct
2 Partially correct 104 ms 456 KB Partially correct
3 Partially correct 75 ms 464 KB Partially correct
4 Partially correct 102 ms 456 KB Partially correct
5 Partially correct 90 ms 456 KB Partially correct
6 Partially correct 93 ms 456 KB Partially correct
7 Partially correct 75 ms 456 KB Partially correct