| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 154531 | Mercenary | Amusement Park (JOI17_amusement_park) | C++14 | 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 "Joi.h"
#include<bits/stdc++.h>
using namespace std;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
const static int maxn = 1e4 + 5;
static int lab[maxn];
static int nTime = 0;
static int id[maxn];
static long long res = 0;
static long long cal = 0;
static vector<int> adj[maxn];
fill_n(lab,maxn,-1);
function<int(int)> FindLab = [&](int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
};
for(int i = 0 ; i < M ; ++i){
int s = FindLab(A[i]);
int d = FindLab(B[i]);
if(s != d){
if(lab[s] > lab[d])swap(s , d);
lab[s] += lab[d];
lab[d] = s;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
function<void(int,int)> DFS = [&](int u , int par){
id[u] = nTime;
++nTime;
nTime %= 60;
for(int c : adj[u]){
if(c != par){
DFS(c , u);
}
}
};
DFS(0 , -1);
for(int i = 0 ; i < N ; ++i){
MessageBoard(i , (X >> id[i]) & 1);
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
const static int maxn = 1e4 + 5;
static int lab[maxn];
static int nTime = 0;
static int id[maxn];
static long long res = 0;
static long long cal = 0;
static int sub[maxn] , h[maxn];
static long long can[maxn];
static int p[maxn];
static vector<int> adj[maxn];
static vector<int> child[maxn];
fill_n(lab,maxn,-1);
function<int(int)> FindLab = [&](int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
};
for(int i = 0 ; i < M ; ++i){
int s = FindLab(A[i]);
int d = FindLab(B[i]);
if(s != d){
if(lab[s] > lab[d])swap(s , d);
lab[s] += lab[d];
lab[d] = s;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
function<void(int,int)> DFS = [&](int u , int par){
id[u] = nTime;
++nTime;
nTime %= 60;
sub[u] = 1;
for(int c : adj[u]){
if(c != par){
child[u].push_back(c);
p[c] = u;
DFS(c , u);
sub[u] += sub[c];
}
}
};
int lim = 60;
function<void(int,int)> DFS3 = [&](int u , int par){
lim--;
h[u] = -1e9;
if(lim <= 0)return;
can[u] = (1ll << id[u]);
sub[u] = 1;
for(int c : child[u]){
if(c != par){
p[c] = u;
DFS3(c , u);
h[u] = max(h[u] , h[c] + 1);
can[u] |= can[c];
}
}
};
DFS(0 , -1);
function<void(int)> DFS2 = [&](int u){
cal |= (1ll << id[u]);
if(V)res |= (1ll << id[u]);
for(int c : child[u]){
if(__builtin_popcountll(cal) == 60)return;
if((~cal) & can[c]){
V = Move(c);
DFS2(c);
V = Move(u);
}
}
};
function<void(int)> DFS1 = [&](int u){
cal |= (1ll << id[u]);
if(V)res |= (1ll << id[u]);
if(child[u].empty())return;
int best = -1;
for(int c : child[u]){
if(__builtin_popcountll(cal) == 60)return;
if((~cal) & can[c]){
if(best == -1 || h[best] < h[c])best = c;
}
}
for(int c : child[u]){
if(__builtin_popcountll(cal) == 60)return;
if(c == best)continue;
if((~cal) & can[c]){
V = Move(c);
DFS2(c);
V = Move(u);
}
}
if(best != -1 && ((~cal) & can[best])){
V = Move(best);
DFS1(best);
}
};
while(sub[P] < 60){
cal |= (1ll << id[P]);
if(V)res |= (1ll << id[P]);
V = Move(p[P]);
P = p[P];
}
DFS3(P , -1);
DFS1(P);
return res;
}
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
using namespace std;
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000
void Joi(int N, int M, int A[], int B[], long long X, int T);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);
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)
{
int i;
long long max_code;
freopen("sample-01.txt","r",stdin);
scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
for (int 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 (int 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);
// cout << n_move << endl;
if (answer != X) {
WrongAnswer(5);
}
printf("Accepted : #move=%d\n", n_move);
return 0;
}