| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1174206 | Zero_OP | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include "Joi.h"
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
struct DSU{
vi lab;
DSU(int n) : lab(n, -1) {}
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool join(int u, int v){
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
const int MAX = 1e4 + 5;
int depth[MAX], par[MAX], max_depth[MAX], timer_dfs, c[MAX];
vi adj[MAX];
void dfs(int u, int p){
max_depth[u] = depth[u];
for(auto v : adj[u]) if(v != p){
par[v] = u;
depth[v] = depth[u] + 1;
dfs(v, u);
maximize(max_depth[u], max_depth[v]);
}
}
void dfs_mark(int u, int p, ll target){
c[u] = (target >> (depth[u] % 60) & 1);
for(auto v : adj[u]) if(v != p){
dfs_mark(v, u, target);
}
}
void dfs_cover(int u, int p, ll target){
if(timer_dfs == 60) return;
c[u] = timer_dfs++;
for(auto v : adj[u]) if(v != p){
dfs_cover(v, u, target);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
DSU dsu(N);
FOR(i, 0, M){
if(dsu.join(A[i], B[i])){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
}
dfs(0, -1);
fill(c, c + N, -1);
if(max_depth[u] >= 59){
dfs_mark(0, -1, X);
FOR(i, 0, N) MessageBoard(i, c[i]);
} else{
FOR(i, 0, N){
sort(all(adj[i]), [&](int u, int v){ return max_depth[u] < max_depth[v]; });
}
dfs_cover(0, -1, X);
FOR(i, 0, N) {
if(c[i] != -1) MessageBoard(i, c[i]);
else MessageBoard(i, 0);
}
}
}
really fun
#include "Ioi.h"
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
struct DSU{
vi lab;
DSU(int n) : lab(n, -1) {}
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool join(int u, int v){
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
const int MAX = 1e4 + 5;
int depth[MAX], par[MAX], max_depth[MAX], timer_dfs, c[MAX];
vi adj[MAX];
void dfs(int u, int p){
max_depth[u] = depth[u];
for(auto v : adj[u]) if(v != p){
par[v] = u;
depth[v] = depth[u] + 1;
dfs(v, u);
maximize(max_depth[u], max_depth[v]);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
DSU dsu(N);
FOR(i, 0, M){
if(dsu.join(A[i], B[i])){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
}
dfs(0, -1);
ll X = 0;
if(max_depth[0] >= 59){
if(depth[P] >= 59){
X |= (1LL << (depth[P] % 60)) * V;
FOR(i, 1, 59){
P = par[P];
int nxt = Move(P);
X |= (1LL << (depth[P] % 60)) * nxt);
}
return X;
} else{
stack<int> to_root;
X |= (1LL << depth[P]) * V;
int base = P;
while(P != 0){
to_root.push(P);
P = par[P];
int nxt = Move(P);
X |= (1LL << depth[P]) * V;
}
while(!to_root.empty()){
P = to_root.top(); to_root.pop();
Move(P);
}
assert(P == base);
int had = depth[P];
FOR(i, had, 60){
}
}
}
return 0ll;
}