| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 122003 | egorlifar | 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 "Ioi.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
using namespace std;
template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
if (x > y) {
x = y;
return 1;
}
else {
return 0;
}
}
template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
if (x < y) {
x = y;
return 1;
}
else {
return 0;
}
}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
const int MAXN = 10228;
vector<int> g[MAXN];
bool used[MAXN];
vector<int> v[MAXN];
int pr[MAXN];
int it = 0;
int who[MAXN];
int pos[MAXN];
bool was[MAXN];
long long kek[MAXN];
long long ft;
void dfs(int u) {
used[u] = true;
who[u] = it % 60;
it++;
kek[u] = 1LL << who[u];
for (auto h: g[u]) {
if (!used[h]) {
pr[h] = u;
v[u].pb(h);
pos[h] = sz(v[u]) - 1;
dfs(h);
kek[u] |= kek[h];
}
}
}
int cnt;
long long res = 0;
bool bfs(int u) {
for (auto h: v[u]) {
if ((ft & kek[h]) == kek[h]) continue;
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return true;
} else {
if (bfs(h)) {
return true;
}
Move(u);
}
}
return false;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
assert(T <= 10);
for (int i = 0; i < N; i++){
used[i] = false;
}
for (int i = 0; i < M; i++) {
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
for (int i = 0; i < 60; i++) {
was[i] = false;
}
dfs(0);
int cur = P;
was[who[cur]] = true;
res += (1LL << who[cur]) * V;
ft |= 1LL << who[cur];
cnt = 1;
if (bfs(cur)) {
return res;
}
while (true) {
assert(cur != 0);
int fk = pos[cur];
int gg = Move(pr[cur]);
ft |= 1LL << who[pr[cur]];
if (!was[who[pr[cur]]]) {
cnt++;
res += (1LL << who[pr[cur]]) * gg;
}
cur = pr[cur];
if (cnt == 60) {
return res;
}
for (int i = fk + 1; i < sz(v[cur]); i++) {
int h = v[cur][i];
if ((ft & kek[h]) == kek[h]) {
continue;
}
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return res;
}
if (bfs(h)) {
return res;
}
Move(cur);
}
for (int i = 0; i < fk; i++) {
int h = v[cur][i];
if ((ft & kek[h]) == kek[h]) {
continue;
}
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return res;
}
if (bfs(h)) {
return res;
}
Move(cur);
}
}
return 0LL;
}
#include "Ioi.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
using namespace std;
template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
if (x > y) {
x = y;
return 1;
}
else {
return 0;
}
}
template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
if (x < y) {
x = y;
return 1;
}
else {
return 0;
}
}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
const int MAXN = 10228;
vector<int> g[MAXN];
bool used[MAXN];
vector<int> v[MAXN];
int pr[MAXN];
int it = 0;
int who[MAXN];
int pos[MAXN];
bool was[MAXN];
long long kek[MAXN];
long long ft;
void dfs(int u) {
used[u] = true;
who[u] = it % 60;
it++;
kek[u] = 1LL << who[u];
for (auto h: g[u]) {
if (!used[h]) {
pr[h] = u;
v[u].pb(h);
pos[h] = sz(v[u]) - 1;
dfs(h);
kek[u] |= kek[h];
}
}
}
int cnt;
long long res = 0;
bool bfs(int u) {
for (auto h: v[u]) {
if ((ft & kek[h]) == kek[h]) continue;
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return true;
} else {
if (bfs(h)) {
return true;
}
Move(u);
}
}
return false;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
assert(T <= 10);
for (int i = 0; i < N; i++){
used[i] = false;
}
for (int i = 0; i < M; i++) {
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
for (int i = 0; i < 60; i++) {
was[i] = false;
}
dfs(0);
int cur = P;
was[who[cur]] = true;
res += (1LL << who[cur]) * V;
ft |= 1LL << who[cur];
cnt = 1;
if (bfs(cur)) {
return res;
}
while (true) {
assert(cur != 0);
int fk = pos[cur];
int gg = Move(pr[cur]);
ft |= 1LL << who[pr[cur]];
if (!was[who[pr[cur]]]) {
cnt++;
res += (1LL << who[pr[cur]]) * gg;
}
cur = pr[cur];
if (cnt == 60) {
return res;
}
for (int i = fk + 1; i < sz(v[cur]); i++) {
int h = v[cur][i];
if ((ft & kek[h]) == kek[h]) {
continue;
}
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return res;
}
if (bfs(h)) {
return res;
}
Move(cur);
}
for (int i = 0; i < fk; i++) {
int h = v[cur][i];
if ((ft & kek[h]) == kek[h]) {
continue;
}
int gg = Move(h);
ft |= 1LL << who[h];
if (!was[who[h]]) {
cnt++;
was[who[h]] = true;
res += (1LL << who[h]) * gg;
}
if (cnt == 60) {
return res;
}
if (bfs(h)) {
return res;
}
Move(cur);
}
}
return 0LL;
}