oj.uz

Submission #1063678

# Submission time Handle Problem Language Result Execution time Memory
1063678 2024-08-17T23:04:09 Z pawned Game (IOI14_game) C++17
15 / 100
 1 ms 600 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;

bool flag1 = false;	// already have three comps

vi roots;
vi cnts(3, 0);	// count of 01, 02, 12
vi szs(3, 0);
map<int, int> conv;
int ctr = 0;	// how many pairs of comps fully filled
// first pair fully filled is 1, second is 0, last is 1


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

int hasEdge(int u, int v) {
	if (!flag1) {
		if (!dsu.sameset(u, v))
			ccs--;
		dsu.merge(u, v);
		if (ccs == 3) {
			flag1 = true;
			// go into pairing mode
			set<int> setr;	// set of roots
			for (int i = 0; i < N; i++) {
				setr.insert(dsu.root(i));
			}
			for (int x : setr)
				roots.pb(x);
			for (int i = 0; i < 3; i++) {
				szs[i] = dsu.size(roots[i]);
				conv[roots[i]] = i;
			}
/*			cout<<"roots: ";
			for (int x : roots)
				cout<<x<<" ";
			cout<<endl;
			cout<<"szs: ";
			for (int x : szs)
				cout<<x<<" ";
			cout<<endl;*/
		}
		return 1;
	}
	else {
		u = dsu.root(u);
		v = dsu.root(v);
		if (u == v)
			return 1;
		int r1 = conv[u];
		int r2 = conv[v];
		int pos = r1 + r2 - 1;
//		cout<<"r1, r2, pos: "<<r1<<" "<<r2<<" "<<pos<<endl;
		cnts[pos]++;
//		cout<<"cnts["<<pos<<"]: "<<cnts[pos]<<endl;
		if (cnts[pos] == szs[r1] * szs[r2]) {
//			cout<<"orz"<<endl;
			ctr++;
			if (ctr == 1 || ctr == 3)
				return 1;
			else
				return 0;
		}
		else {
			return 0;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 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 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 27.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 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 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 0 ms 448 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 448 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -