oj.uz

Submission #1069024

# Submission time Handle Problem Language Result Execution time Memory
1069024 2024-08-21T14:34:41 Z Joshua_Andersson Mechanical Doll (IOI18_doll) C++14
100 / 100
 118 ms 10324 KB 
#include "doll.h"

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

const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

int n;
int ind = 1;
vi state;
vi x, y;
int k=0;
vi exitcnt;
int numexits = 0;
int build_tree(int d, vi& x, vi& y)
{
	int u = ind++;
	if (d==0)
	{
		exitcnt[u] = 2;
		numexits += 2;
		x[u] = inf;
		y[u] = inf;
		return u;
	}
	y[u] = build_tree(d - 1, x, y);
	x[u] = build_tree(d - 1, x, y);
	exitcnt[u] = exitcnt[x[u]] + exitcnt[y[u]];
	return u;
}

void killc(int u, vi& x, vi& y)
{
	if (u == inf) return;
	if (x[u]!=inf)
	{
		exitcnt[x[u]] = 0;
		killc(x[u], x, y);
		x[u] = inf;
	}
	if (y[u]!=inf)
	{
		exitcnt[y[u]] = 0;
		killc(y[u], x, y);
		y[u] = inf;
	}
}

bool kill(int u, vi& x, vi& y)
{
	if (u == inf) return false;
	if (numexits-exitcnt[u]>=n+1)
	{
		numexits -= exitcnt[u];
		killc(u, x, y);
		return true;
	}
	
	if (kill(x[u], x, y))
	{
		exitcnt[u] -= exitcnt[x[u]];
		x[u] = 1;
	}
	if (kill(y[u], x, y))
	{
		exitcnt[u] -= exitcnt[y[u]];
		y[u] = 1;
	}
	exitcnt[u] = 0;
	if (x[u] != inf) exitcnt[u] += exitcnt[x[u]];
	if (y[u] != inf) exitcnt[u] += exitcnt[y[u]];
	return false;
}

int* lastv = 0;
int statesum = 0;
void traverse(int u, int t)
{
	int& v = state[u]?y[u]:x[u];
	if (v == -1) return;
	statesum += state[u] == 0 ? 1 : -1;
	state[u] ^= 1;
	if (v==inf)
	{
		lastv = &v;
		v = -t;
		return;
	}
	traverse(v, t);
}

void create_circuit(int m, std::vector<int> a)
{
	n = sz(a);
	vi c(m + 1, -1);
	c[0] = a[0];
	n--;
	a.erase(a.begin());
	while ((1<<(k+1))<=n)
	{
		k++;
	}

	state.resize(1 << (k+1));
	x.resize(1 << (k+1), inf);
	y.resize(1 << (k+1), inf);
	exitcnt.resize(1 << (k+1), 0);
	build_tree(k, x, y);
	kill(1, x, y);
	rep(i, n)
	{
		traverse(1, a[i]);
	}
	repp(i, n, (1<<(k+1)))
	{
		traverse(1, -1);
		if (statesum == 0)
		{
			*lastv = 0;
			break;
		}
	}

	while (x.back()==inf&&y.back()==inf)
	{
		x.pop_back();
		y.pop_back();
	}
	rep(i, sz(x)) x[i] *= -1, y[i] *= -1;
	rep(i, sz(x))
	{
		if (x[i] == -inf) x[i] = -1;
		if (y[i] == -inf) y[i] = -1;
	}
	x.erase(x.begin());
	y.erase(y.begin());
	
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 31 ms 4192 KB Output is correct
3 Correct 33 ms 4712 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 45 ms 5980 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 31 ms 4192 KB Output is correct
3 Correct 33 ms 4712 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 45 ms 5980 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 79 ms 6228 KB Output is correct
9 Correct 65 ms 8800 KB Output is correct
10 Correct 92 ms 10324 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 31 ms 4192 KB Output is correct
3 Correct 33 ms 4712 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 45 ms 5980 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 79 ms 6228 KB Output is correct
9 Correct 65 ms 8800 KB Output is correct
10 Correct 92 ms 10324 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 118 ms 10004 KB Output is correct
15 Correct 68 ms 8016 KB Output is correct
16 Correct 110 ms 9884 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 98 ms 10064 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 0 ms 344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 55 ms 5460 KB Output is correct
3 Correct 69 ms 7608 KB Output is correct
4 Correct 87 ms 9156 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 55 ms 5460 KB Output is correct
3 Correct 69 ms 7608 KB Output is correct
4 Correct 87 ms 9156 KB Output is correct
5 Correct 102 ms 9696 KB Output is correct
6 Correct 105 ms 9736 KB Output is correct
7 Correct 96 ms 9776 KB Output is correct
8 Correct 95 ms 9432 KB Output is correct
9 Correct 66 ms 7640 KB Output is correct
10 Correct 94 ms 9304 KB Output is correct
11 Correct 100 ms 9040 KB Output is correct
12 Correct 83 ms 7508 KB Output is correct
13 Correct 55 ms 5960 KB Output is correct
14 Correct 71 ms 8004 KB Output is correct
15 Correct 69 ms 8004 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 59 ms 5576 KB Output is correct
18 Correct 55 ms 5456 KB Output is correct
19 Correct 82 ms 7620 KB Output is correct
20 Correct 95 ms 9192 KB Output is correct
21 Correct 100 ms 9176 KB Output is correct
22 Correct 91 ms 9044 KB Output is correct