| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 442675 | valerikk | Amusement Park (JOI17_amusement_park) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
void Joi(int N, int M, int A[], int B[], long long X, int T);
void MessageBoard(int attr, int msg);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);
int Move(int dest);
#else
#include "amusement_park.h"
#endif
namespace solution {
const int N = 10010;
int n, m;
vector<int> g[N];
bool used[N];
vector<pair<int, int>> edges[N], all_edges;
int bit_id[N], val[N];
int cnt[N];
bool in[N];
void dfs(int v) {
used[v] = true;
for (int u : g[v]) {
if (!used[u]) {
all_edges.emplace_back(v, u);
dfs(u);
}
}
}
void dfs_move(int v) {
used[v] = true;
for (int u : g[v]) {
if (!used[u] && in[u]) {
val[u] = Move(u);
dfs_move(u);
Move(v);
}
}
}
void build_graph(int a[], int b[]) {
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 0; i < m; i++) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
for (int i = 0; i < n; i++) {
used[i] = false;
sort(g[i].begin(), g[i].end());
}
all_edges.clear();
dfs(0);
}
void build_comps() {
for (int i = 0; i < n; i++) {
edges[i].clear();
bit_id[i] = -1;
cnt[i] = 0;
}
bit_id[0] = 0;
for (int i = 0; i < 59; i++) {
edges[0].push_back(all_edges[i]);
bit_id[all_edges[i].second] = i + 1;
}
for (int i = 0; i < 59; i++) edges[all_edges[i].second] = edges[0];
for (auto [from, to] : all_edges) {
if (bit_id[to] == -1) {
for (auto [v, u] : edges[from]) {
cnt[v]++;
cnt[u]++;
}
int del = -1;
for (auto [v, u] : edges[from]) {
if (v != from && cnt[v] == 1) del = v;
if (u != from && cnt[u] == 1) del = u;
}
for (auto [v, u] : edges[from]) {
cnt[v]--;
cnt[u]--;
}
assert(del != -1);
bit_id[to] = bit_id[del];
for (auto [v, u] : edges[from]) {
if (v == del || u == del) continue;
edges[to].emplace_back(v, u);
}
edges[to].emplace_back(from, to);
}
}
}
void joi(int n_, int m_, int a[], int b[], ll x, int subtask) {
n = n_, m = m_;
build_graph(a, b);
build_comps();
for (int i = 0; i < n; i++) MessageBoard(i, (x >> bit_id[i]) & 1);
}
ll ioi(int n_, int m_, int a[], int b[], int start, int sv, int subtask) {
n = n_, m = m_;
build_graph(a, b);
build_comps();
for (int i = 0; i < n; i++) {
val[i] = -1;
used[i] = false;
in[i] = false;
}
val[start] = sv;
for (auto [v, u] : edges[start]) {
in[v] = true;
in[u] = true;
}
dfs_move(start);
vector<int> have(60, -1);
for (int i = 0; i < n; i++) {
if (val[i] != -1) have[bit_id[i]] = val[i];
}
ll res = 0;
for (int i = 0; i < 60; i++) {
if (have[i]) res += 1ll << i;
}
return res;
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
return solution::joi(N, M, A, B, X, T);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
return solution::ioi(N, M, A, B, P, V, T);
}
#ifdef LOCAL
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000
static int N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;
void WrongAnswer(int e)
{
printf("Wrong Answer[%d]\n", e);
exit(1);
}
void MessageBoard(int attr, int msg)
{
if (!(0 <= attr && attr <= N - 1)) {
WrongAnswer(1);
}
if (given_msg[attr] != -1) {
WrongAnswer(2);
}
if (!(msg == 0 || msg == 1)) {
WrongAnswer(3);
}
given_msg[attr] = msg;
}
int Move(int dest)
{
if (!(0 <= dest && dest <= N - 1)) {
WrongAnswer(6);
}
if (!edges.count({ pos, dest })) {
WrongAnswer(7);
}
++n_move;
if (n_move > MOVEMAX) {
WrongAnswer(8);
}
pos = dest;
return given_msg[pos];
}
int main(void)
{
freopen("input.txt", "r", stdin);
int i;
scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
for (i = 0; i < M; ++i) {
scanf("%d%d", &(A[i]), &(B[i]));
edges.insert({ A[i], B[i] });
edges.insert({ B[i], A[i] });
}
for (i = 0; i < N; ++i) {
given_msg[i] = -1;
}
Joi(N, M, A, B, X, T);
for (i = 0; i < N; ++i) {
if (given_msg[i] == -1) {
WrongAnswer(4);
}
}
n_move = 0;
pos = P;
long long answer = Ioi(N, M, A, B, P, given_msg[P], T);
if (answer != X) {
WrongAnswer(5);
}
printf("Accepted : #move=%d\n", n_move);
return 0;
}
#endif