Submission #49733

#TimeUsernameProblemLanguageResultExecution timeMemory
49733imeimi2000Snowy Roads (JOI16_snowy)C++17
100 / 100
27 ms2272 KiB
#include "Anyalib.h" #include <algorithm> #include <vector> using namespace std; const static int t = 11; typedef pair<int, int> pii; const static int MAXN = 500; static int n; static vector<pii> edge[MAXN]; static int s[MAXN], e[MAXN]; static pii close[MAXN]; static void dfs1(int x, int p, pii cl) { if (cl.first > t) { cl = pii(0, x); } close[x] = cl; ++cl.first; for (pii i : edge[x]) { if (i.second == p) continue; dfs1(i.second, x, cl); pii tp = close[i.second]; tp.first += 2; cl = min(cl, tp); } } static int dist[MAXN]; static int par[MAXN]; static void dfs2(int x, int p, int d, int C[]) { dist[x] = d; for (pii i : edge[x]) { if (i.second == p) continue; par[i.second] = C[i.first]; dfs2(i.second, x, d + C[i.first], C); } } void InitAnya(int N , int A[] , int B[]) { n = N; for (int i = 0; i < n - 1; ++i) { edge[A[i]].emplace_back(i, B[i]); edge[B[i]].emplace_back(i, A[i]); } dfs1(0, -1, pii(20, -1)); int p = 0; for (int i = 0; i < n; ++i) { s[i] = p; p = p + (close[i].first ? 1 : 10); e[i] = p - 1; } } void Anya(int C[]) { dfs2(0, -1, 0, C); for (int i = 0; i < n; ++i) { Save(s[i], par[i]); for (int j = s[i] + 1; j <= e[i]; ++j) { Save(j, dist[i] & 1); dist[i] >>= 1; } } }
#include "Borislib.h" #include <algorithm> #include <vector> using namespace std; const static int t = 11; typedef pair<int, int> pii; const static int MAXN = 500; static int n; static vector<pii> edge[MAXN]; static int s[MAXN], e[MAXN]; static pii close[MAXN]; static int par[MAXN]; static int dep[MAXN]; static void dfs1(int x, int p, pii cl) { par[x] = p; if (cl.first > t) { cl = pii(0, x); } close[x] = cl; ++cl.first; for (pii i : edge[x]) { if (i.second == p) continue; dep[i.second] = dep[x] + 1; dfs1(i.second, x, cl); pii tp = close[i.second]; tp.first += 2; cl = min(cl, tp); } } void InitBoris(int N , int A[] , int B[]) { n = N; for (int i = 0; i < n - 1; ++i) { edge[A[i]].emplace_back(i, B[i]); edge[B[i]].emplace_back(i, A[i]); } dfs1(0, -1, pii(20, -1)); int p = 0; for (int i = 0; i < n; ++i) { s[i] = p; p = p + (close[i].first ? 1 : 10); e[i] = p - 1; } } int Boris(int x) { int y = close[x].second; int ret = 0; for (int i = e[y]; i > s[y]; --i) { ret <<= 1; ret += Ask(i); } while (dep[x] < dep[y]) { ret -= Ask(s[y]); y = par[y]; } while (dep[x] > dep[y]) { ret += Ask(s[x]); x = par[x]; } while (x != y) { ret += Ask(s[x]) - Ask(s[y]); x = par[x]; y = par[y]; } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...