oj.uz

Submission #1063694

# Submission time Handle Problem Language Result Execution time Memory
1063694 2024-08-17T23:35:43 Z pawned Game (IOI14_game) C++17
15 / 100
 13 ms 18232 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "game.h"

struct DSU {
	vi e;
	void init(int N) {
		e = vi(N, -1);
	}
	int root(int x) {
		if (e[x] < 0) {
			return x;
		}
		else {
			e[x] = root(e[x]);
			return e[x];
		}
	}
	bool sameset(int x, int y) {
		return(root(x) == root(y));
	}
	bool merge(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)
			return false;
		if (-e[x] < -e[y])
			swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
	int size(int x) {
		return -e[root(x)];
	}
};

const int MAX = 1505;

int N;

DSU dsu;
int ccs;

vector<vi> adj(MAX, vi(MAX, 0));
// 0 if not done
// 1 if missing
// 2 if filled

void initialize(int n) {
	N = n;
	dsu.init(N);
	ccs = N;
}

int hasEdge(int u, int v) {
/*	cout<<"adj: "<<endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout<<adj[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"ccs: "<<ccs<<endl;*/
	// check if connecting u to v makes any "bad triangle"
	// bad triangle u, v, w if (u, v) = 2, (u, w) = 2, and (v, w) isn't 1
	// or if (v, w) = 2 and (u, w) isn't 1
	bool can = true;
	for (int i = 0; i < N; i++) {
		if (adj[u][i] == 2 && adj[v][i] != 1)
			can = false;
		if (adj[v][i] == 2 && adj[u][i] != 1)
			can = false;
	}
	if (can && ccs >= 3) {
		adj[u][v] = 2;
		adj[v][u] = 2;
		if (!dsu.sameset(u, v)) {
			dsu.merge(u, v);
			ccs--;
		}
		return 1;
	}
	else {
		adj[u][v] = 1;
		adj[v][u] = 1;
		return 0;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18008 KB Output is correct
2 Correct 9 ms 18224 KB Output is correct
3 Correct 9 ms 18008 KB Output is correct
4 Correct 9 ms 18012 KB Output is correct
5 Correct 8 ms 18012 KB Output is correct
6 Correct 8 ms 18128 KB Output is correct
7 Correct 12 ms 18012 KB Output is correct
8 Correct 8 ms 18008 KB Output is correct
9 Correct 10 ms 18012 KB Output is correct
10 Correct 8 ms 18100 KB Output is correct
11 Correct 7 ms 18012 KB Output is correct
12 Correct 8 ms 18012 KB Output is correct
13 Correct 8 ms 18012 KB Output is correct
14 Correct 8 ms 18012 KB Output is correct
15 Correct 8 ms 18012 KB Output is correct
16 Correct 8 ms 17992 KB Output is correct
17 Correct 9 ms 18012 KB Output is correct
18 Correct 9 ms 18012 KB Output is correct
19 Correct 8 ms 18012 KB Output is correct
20 Correct 8 ms 17976 KB Output is correct
21 Correct 8 ms 18012 KB Output is correct
22 Correct 8 ms 18012 KB Output is correct
23 Correct 7 ms 18012 KB Output is correct
24 Correct 9 ms 18012 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18008 KB Output is correct
2 Correct 11 ms 18020 KB Output is correct
3 Correct 9 ms 18012 KB Output is correct
4 Correct 8 ms 18180 KB Output is correct
5 Correct 8 ms 18012 KB Output is correct
6 Correct 8 ms 18132 KB Output is correct
7 Correct 7 ms 18012 KB Output is correct
8 Correct 8 ms 18012 KB Output is correct
9 Correct 9 ms 18012 KB Output is correct
10 Correct 9 ms 18012 KB Output is correct
11 Correct 9 ms 18012 KB Output is correct
12 Correct 8 ms 18172 KB Output is correct
13 Correct 8 ms 18136 KB Output is correct
14 Correct 8 ms 18012 KB Output is correct
15 Correct 9 ms 18012 KB Output is correct
16 Correct 8 ms 17976 KB Output is correct
17 Correct 8 ms 18012 KB Output is correct
18 Correct 8 ms 18008 KB Output is correct
19 Correct 8 ms 18012 KB Output is correct
20 Correct 8 ms 17972 KB Output is correct
21 Correct 8 ms 18008 KB Output is correct
22 Correct 8 ms 18012 KB Output is correct
23 Correct 7 ms 18108 KB Output is correct
24 Correct 8 ms 18012 KB Output is correct
25 Incorrect 8 ms 18012 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18012 KB Output is correct
2 Correct 7 ms 18012 KB Output is correct
3 Correct 8 ms 18012 KB Output is correct
4 Correct 8 ms 18196 KB Output is correct
5 Correct 8 ms 18008 KB Output is correct
6 Correct 8 ms 18024 KB Output is correct
7 Correct 10 ms 18008 KB Output is correct
8 Correct 8 ms 18044 KB Output is correct
9 Correct 9 ms 18012 KB Output is correct
10 Correct 9 ms 18036 KB Output is correct
11 Correct 9 ms 18012 KB Output is correct
12 Correct 9 ms 18012 KB Output is correct
13 Correct 8 ms 18012 KB Output is correct
14 Correct 8 ms 18012 KB Output is correct
15 Correct 9 ms 18140 KB Output is correct
16 Correct 8 ms 18008 KB Output is correct
17 Correct 8 ms 18012 KB Output is correct
18 Correct 8 ms 18012 KB Output is correct
19 Correct 8 ms 18012 KB Output is correct
20 Correct 8 ms 18232 KB Output is correct
21 Correct 8 ms 18012 KB Output is correct
22 Correct 8 ms 18068 KB Output is correct
23 Correct 8 ms 18012 KB Output is correct
24 Correct 8 ms 18012 KB Output is correct
25 Incorrect 9 ms 18012 KB Output isn't correct
26 Halted 0 ms 0 KB -