Submission #926526

#TimeUsernameProblemLanguageResultExecution timeMemory
926526daoquanglinh2007Amusement Park (JOI17_amusement_park)C++17
100 / 100
20 ms5132 KiB
#include "Joi.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int NM = 1e4; namespace _Joi{ vector <int> g[NM+5], son[NM+5]; int parent[NM+5], dep[NM+5]; bool vis[NM+5], in_max_path[NM+5]; int MAX_DEP = 0, cnt = 0; void dfs(int u, int p){ parent[u] = p; if (p != -1) son[p].push_back(u); dep[u] = (p == -1 ? 0 : dep[p]+1); MAX_DEP = max(MAX_DEP, dep[u]); vis[u] = 1; for (int v : g[u]){ if (vis[v]) continue; dfs(v, u); } } void build(int u, ll X){ cnt++; MessageBoard(u, (X>>(cnt-1))&1); vis[u] = 1; for (int v : son[u]){ if (!in_max_path[v]) continue; build(v, X); } for (int v : son[u]){ if (in_max_path[v]) continue; if (cnt < 60) build(v, X); } } void solve(int N, int M, int A[], int B[], ll X, int T){ assert(T >= 1 && T <= 5); for (int i = 0; i < M; i++){ g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } dfs(0, -1); if (MAX_DEP >= 60){ for (int i = 0; i < N; i++) MessageBoard(i, (X>>(dep[i]%60))&1); return; } bool found = 0; for (int i = 0; i < N; i++) if (dep[i] == MAX_DEP && !found){ found = 1; for (int j = i; j != -1; j = parent[j]){ in_max_path[j] = 1; } } for (int i = 0; i < N; i++) vis[i] = 0; build(0, X); for (int i = 0; i < N; i++) if (!vis[i]) MessageBoard(i, 0); } } void Joi(int N, int M, int A[], int B[], ll X, int T){ _Joi::solve(N, M, A, B, X, T); }
#include "Ioi.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int NM = 1e4; namespace _Ioi{ vector <int> g[NM+5], son[NM+5]; int parent[NM+5], dep[NM+5]; bool vis[NM+5], in_max_path[NM+5]; int MAX_DEP = 0, cnt = 0; int L[NM+5], f[NM+5]; ll X = 0; void dfs(int u, int p){ parent[u] = p; if (p != -1) son[p].push_back(u); dep[u] = (p == -1 ? 0 : dep[p]+1); MAX_DEP = max(MAX_DEP, dep[u]); vis[u] = 1; for (int v : g[u]){ if (vis[v]) continue; dfs(v, u); } } void build(int u){ cnt++; L[u] = cnt-1; for (int v : son[u]){ if (!in_max_path[v]) continue; build(v); } for (int v : son[u]){ if (in_max_path[v]) continue; if (cnt < 60) build(v); } } void calc(int u){ f[u] = dep[u]; for (int v : son[u]){ calc(v); f[u] = max(f[u], f[v]); } } void get_ans(int u, int val){ if (val) X += (1LL<<L[u]); for (int v : son[u]){ if (L[v] == -1) continue; if (in_max_path[v]) continue; get_ans(v, Move(v)); Move(u); } for (int v : son[u]){ if (L[v] == -1) continue; if (!in_max_path[v]) continue; get_ans(v, Move(v)); } } ll solve(int N, int M, int A[], int B[], int P, int V, int T){ assert(T >= 1 && T <= 5); for (int i = 0; i < M; i++){ g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } dfs(0, -1); if (MAX_DEP >= 60){ if (dep[P] >= 60){ if (V) X += (1LL<<(dep[P]%60)); for (int i = 1; i < 60; i++){ P = parent[P]; V = Move(P); if (V) X += (1LL<<(dep[P]%60)); } } else{ while (P > 0){ P = parent[P]; V = Move(P); } calc(0); if (V) X++; for (int i = 1; i < 60; i++){ for (int nxt : son[P]){ if (f[nxt] < 59) continue; P = nxt; V = Move(nxt); if (V) X += (1LL<<i); break; } } } return X; } bool found = 0; for (int i = 0; i < N; i++) if (dep[i] == MAX_DEP && !found){ found = 1; for (int j = i; j != -1; j = parent[j]){ in_max_path[j] = 1; } } for (int i = 0; i < N; i++) L[i] = -1; build(0); while (P > 0){ P = parent[P]; V = Move(P); } get_ans(0, V); return X; } } ll Ioi(int N, int M, int A[], int B[], int P, int V, int T){ return _Ioi::solve(N, M, A, B, P, V, T); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...