oj.uz

Submission #322021

# Submission time Handle Problem Language Result Execution time Memory
322021 2020-11-13T19:41:10 Z anakib1 Split the Attractions (IOI19_split) C++17
18 / 100
 142 ms 16364 KB 
//나는 가상 소녀들에게 큰 호감이 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem "a"

template<typename A, typename B, typename C>
struct triple {
	A X;
	B Y;
	C Z;
	triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
	return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
	if (a.X != b.X)
		return a.X < b.X;
	if (a.Y != b.Y)
		return a.Y < b.Y;
	return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
	ofs << "( " << p.F << " , " << p.S << " )";
	return ofs;
}
template<typename T>
void print(T a) {
	for (auto i : a)
		cout << i << ' ';
	cout << '\n';
}
template<typename T>
T max(T a, T b, T c) {
	return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c) {
	return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a) {
	return *min_element(all(a));
}
template<typename T, typename D>
D max(T a) {
	return *max_element(all(a));
}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
#include "split.h"


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<pii> z({ {a,1},{b,2},{c,3} });
	SORT(z);
	a = z[0].first;
	b = z[1].first;
	c = z[2].first;
	vector<vi> g(n);
	rngi(i, sz(q)) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
	vi usd(n);
	vi s(n), h(n);
	vi ans(n);
	function<int(int, int)> dfs = [&](int v, int hh) {
		usd[v] = s[v] = 1; h[v] = hh;
		for (auto to : g[v]) if (!usd[to])s[v] += dfs(to, hh + 1);
		return s[v];
	};
	function<void(int, int)> dfs2 = [&](int v, int x) {
		if (x == 1) {
			a--;
			if (a < 0)return;
		}
		if (x == 2) {
			b--;
			if (b < 0)return;
		}
		ans[v] = x;
		for (auto to : g[v]) if (!ans[to])dfs2(to, x);
	};
	dfs(0, 0);
	rngi(i, n - 1) {
		int v = p[i], u = q[i];
		if (h[v] < h[u]) swap(v, u);
		if (s[v] >= a && n - s[v] >= b) {
			ans[v] = 1; ans[u] = 2;
			dfs2(v, 1);
			dfs2(u, 2);
			rngi(j, n) if (!ans[j]) ans[j] = z[2].second; else ans[j] = z[ans[j] - 1].second;
			return ans;
		}
	}
	return vi(n, 0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB ok, correct split
2 Correct 0 ms 364 KB ok, correct split
3 Correct 0 ms 364 KB ok, correct split
4 Correct 1 ms 364 KB ok, correct split
5 Correct 1 ms 364 KB ok, correct split
6 Correct 1 ms 364 KB ok, correct split
7 Correct 100 ms 14828 KB ok, correct split
8 Correct 84 ms 13036 KB ok, correct split
9 Correct 86 ms 12524 KB ok, correct split
10 Correct 81 ms 15212 KB ok, correct split
11 Correct 101 ms 15340 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB ok, correct split
2 Correct 1 ms 364 KB ok, correct split
3 Correct 0 ms 364 KB ok, correct split
4 Correct 142 ms 14700 KB ok, correct split
5 Correct 92 ms 10220 KB ok, correct split
6 Correct 78 ms 16364 KB ok, correct split
7 Correct 91 ms 14140 KB ok, correct split
8 Correct 133 ms 13616 KB ok, correct split
9 Correct 88 ms 10220 KB ok, correct split
10 Correct 58 ms 10084 KB ok, correct split
11 Correct 58 ms 10084 KB ok, correct split
12 Correct 60 ms 10468 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB ok, correct split
2 Incorrect 82 ms 9452 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB ok, correct split
2 Correct 1 ms 364 KB ok, no valid answer
3 Correct 1 ms 364 KB ok, correct split
4 Correct 1 ms 364 KB ok, correct split
5 Correct 1 ms 364 KB ok, correct split
6 Correct 1 ms 364 KB ok, correct split
7 Correct 1 ms 364 KB ok, correct split
8 Correct 1 ms 364 KB ok, correct split
9 Correct 3 ms 748 KB ok, correct split
10 Incorrect 3 ms 620 KB invalid split: #1=33, #2=2398, #3=69
11 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB ok, correct split
2 Correct 0 ms 364 KB ok, correct split
3 Correct 0 ms 364 KB ok, correct split
4 Correct 1 ms 364 KB ok, correct split
5 Correct 1 ms 364 KB ok, correct split
6 Correct 1 ms 364 KB ok, correct split
7 Correct 100 ms 14828 KB ok, correct split
8 Correct 84 ms 13036 KB ok, correct split
9 Correct 86 ms 12524 KB ok, correct split
10 Correct 81 ms 15212 KB ok, correct split
11 Correct 101 ms 15340 KB ok, correct split
12 Correct 1 ms 364 KB ok, correct split
13 Correct 1 ms 364 KB ok, correct split
14 Correct 0 ms 364 KB ok, correct split
15 Correct 142 ms 14700 KB ok, correct split
16 Correct 92 ms 10220 KB ok, correct split
17 Correct 78 ms 16364 KB ok, correct split
18 Correct 91 ms 14140 KB ok, correct split
19 Correct 133 ms 13616 KB ok, correct split
20 Correct 88 ms 10220 KB ok, correct split
21 Correct 58 ms 10084 KB ok, correct split
22 Correct 58 ms 10084 KB ok, correct split
23 Correct 60 ms 10468 KB ok, correct split
24 Correct 0 ms 364 KB ok, correct split
25 Incorrect 82 ms 9452 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -