| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 946897 | mansur | 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 "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int NN = 1e4;
int d[2][NN];
vector<int> g[NN];
int get(int x, int k, int n) {
for (int i = 0; i < n; i++) d[k][i] = -1;
queue<int> q;
q.push(x);
int mx = x;
d[k][x] = 0;
while (sz(q)) {
x = q.front();
q.pop();
for (int to: g[x]) {
if (d[k][to] == -1) {
d[k][to] = d[k][x] + 1;
q.push(to);
}
}
}
for (int i = 0; i < n; i++) {
if (d[k][i] > d[k][mx]) {
mx = i;
}
}
return mx;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for (int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
int a = get(0, 0, N);
get(a, 1, N);
for (int i = 0; i < N; i++) {
d[1][i] %= 60;
MessageBoard(i, (X >> d[1][i] & 1));
}
}
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int NN = 1e4;
int d[2][NN];
vector<int> g[NN];
int get(int x, int k, int n) {
for (int i = 0; i < n; i++) d[k][i] = -1;
queue<int> q;
q.push(x);
int mx = x;
d[k][x] = 0;
while (sz(q)) {
x = q.front();
q.pop();
for (int to: g[x]) {
if (d[k][to] == -1) {
d[k][to] = d[k][x] + 1;
q.push(to);
}
}
}
for (int i = 0; i < n; i++) {
if (d[k][i] > d[k][mx]) {
mx = i;
}
}
return mx;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for (int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
int a = get(0, 0, N);
get(a, 1, N);
for (int i = 0; i < N; i++) {
d[1][i] %= 60;
MessageBoard(i, (X >> d[1][i] & 1));
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int Nn = 1e4;
int dd[2][Nn], nxt[Nn], prv[Nn];
vector<int> gg[Nn];
int gett(int x, int k, int n) {
for (int i = 0; i < n; i++) dd[k][i] = -1;
queue<int> q;
q.push(x);
int s = x;
dd[k][x] = 0;
while (sz(q)) {
x = q.front();
q.pop();
for (int to: gg[x]) {
if (dd[k][to] == -1) {
dd[k][to] = dd[k][x] + 1;
prv[to] = x;
q.push(to);
}
}
}
int mx = s;
for (int i = 0; i < n; i++) {
if (dd[k][i] > dd[k][mx]) {
mx = i;
}
}
while (mx != s) {
nxt[prv[mx]] = mx;
mx = prv[mx];
}
return mx;
}
long long Ioi(int N, int M, int A[], int B[], int p, int v, int T) {
for (int i = 0; i < M; i++) {
gg[A[i]].push_back(B[i]);
gg[B[i]].push_back(A[i]);
}
int a = gett(0, 0, N);
ll ans = 0;
int b = gett(a, 1, N);
if ((a != 0 || b != N - 1) && (a != N - 1 || b != 0)) cout << 5 / 0;
for (int i = 1; i <= 60; i++) {
ll b = (dd[1][p] % 60);
if (v) ans += (1ll << b);
bool ok = 0;
for (int to: gg[p]) {
if (dd[1][to] + 1 == dd[1][p]) {
v = Move(to);
p = to;
ok = 1;
break;
}
}
if (!ok) {
ans = 0;
for (ll j = 0; j < 60; j++) {
ans += (1ll << j) * v;
v = Move(nxt[p]);
p = nxt[p];
}
return ans;
}
}
return ans;
}