Submission #39835

#TimeUsernameProblemLanguageResultExecution timeMemory
39835cheater2kSnowy Roads (JOI16_snowy)C++14
35 / 100
22 ms4188 KiB
#include "Anyalib.h" #include <bits/stdc++.h> using namespace std; namespace A { const int N = 505; int n; int dep[N]; int snowy[N]; int w[N]; // for edges int mod; int where[N]; vector< pair<int,int> > G[N]; vector<int> cand; void dfs(int u) { for (auto e : G[u]) { int v = e.second; dep[v] = dep[u] + 1; dfs(v); } } void redfs(int u) { for (auto e : G[u]) { int id = e.first, v = e.second; snowy[v] = snowy[u] + w[id]; redfs(v); } } void init() { dfs(0); vector<int> buf[10]; for (int i = 0; i < n; ++i) { buf[dep[i] % 10].push_back(i); } mod = 0; for (int i = 1; i < 10; ++i) { if (buf[i].size() < buf[mod].size()) mod = i; } cand = buf[mod]; } void solve() { for (int i = 0; i < n; ++i) snowy[i] = 0; redfs(0); // save the edges into bits from 0 to N - 2 for (int i = 0; i < n - 1; ++i) { Save(i, w[i]); } // save the "snowy" values of the vertices that are candidates // each has 9 bits int cur = n - 1; for (int u : cand) { where[u] = cur; for (int i = 0; i < 9; ++i) { Save(cur, snowy[u] >> i & 1); ++cur; } } assert(cur < 1000); } } void InitAnya(int N , int A[] , int B[]) { A::n = N; for (int i = 0; i < N - 1; ++i) { A::G[A[i]].push_back(make_pair(i, B[i])); } A::init(); } void Anya(int C[]) { for (int i = 0; i < A::n - 1; ++i) { A::w[i] = C[i]; } A::solve(); }
#include "Borislib.h" #include <bits/stdc++.h> using namespace std; namespace B { const int N = 505; int n; int par[N], topar[N]; int dep[N]; int w[N]; // for edges int mod; int where[N]; vector< pair<int,int> > G[N]; vector<int> cand; void dfs(int u) { for (auto e : G[u]) { int v = e.second; dep[v] = dep[u] + 1; dfs(v); } } void init() { dfs(0); vector<int> buf[10]; for (int i = 0; i < n; ++i) { buf[dep[i] % 10].push_back(i); } mod = 0; for (int i = 1; i < 10; ++i) { if (buf[i].size() < buf[mod].size()) mod = i; } cand = buf[mod]; // where int cur = n - 1; for (int u : cand) { where[u] = cur; cur += 9; } } int solve(int u) { int ret = 0; while(u && dep[u] % 10 != mod) { ret += Ask(topar[u]); u = par[u]; } if (dep[u] % 10 == mod) { int start = where[u]; int cur = 0; for (int i = start; i < start + 9; ++i) { cur += (1 << (i - start)) * Ask(i); } ret += cur; } return ret; } } void InitBoris(int N , int A[] , int B[]) { B::n = N; for (int i = 0; i < N - 1; ++i) { B::par[B[i]] = A[i]; B::topar[B[i]] = i; B::G[A[i]].push_back(make_pair(i, B[i])); } B::init(); } int Boris(int city) { return B::solve(city); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...