oj.uz

Submission #143690

# Submission time Handle Problem Language Result Execution time Memory
143690 2019-08-14T22:43:44 Z qkxwsm Split the Attractions (IOI19_split) C++14
11 / 100
 109 ms 10492 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 100013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, A, B, C;
vi edge[MAXN];
vi ans;

vi find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	N = n; A = a; B = b; C = c; ans.resize(N);
	FOR(i, 0, SZ(p))
	{
		int u = p[i], v = q[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	FOR(i, 0, N) ans[i] = -1;
	// cerr << "HUH\n";
	q.clear(); q.PB(0); b = 0;
	while(!q.empty())
	{
		int u = q.back(); q.pop_back();
		ans[u] = 2; b++;
		// cerr << "MARK " << u << endl;
		if (b == B) break;
		for (int v : edge[u])
		{
			if (ans[v] == -1)
			{
				// cerr << u << " -> " << v << endl;
				ans[v] = -2;
				q.PB(v);
			}
		}
	}
	FOR(i, 0, N)
	{
		if (ans[i] != 2) ans[i] = 3;
	}
	FOR(i, 0, N)
	{
		if (ans[i] == 3)
		{
			ans[i] = 1;
			break;
		}
	}
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 86 ms 9244 KB ok, correct split
5 Correct 67 ms 8188 KB ok, correct split
6 Correct 66 ms 8188 KB ok, correct split
7 Correct 71 ms 8184 KB ok, correct split
8 Correct 109 ms 10492 KB ok, correct split
9 Correct 67 ms 8184 KB ok, correct split
10 Correct 58 ms 8560 KB ok, correct split
11 Correct 59 ms 8560 KB ok, correct split
12 Correct 61 ms 8560 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB invalid split: #1=1, #2=2, #3=6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -