Submission #126110

#TimeUsernameProblemLanguageResultExecution timeMemory
126110tjd229City (JOI17_city)C++14
100 / 100
572 ms70616 KiB
#include "Encoder.h" #include <vector> using namespace std; vector<int> edge[250000]; vector<int> range; int in[250000],p[250000]; int cnt; void dfs(int x,int from) { in[x] =cnt++; for (auto to : edge[x]) { if (to == from) continue; dfs(to, x); } if (in[x] == cnt - 1) return; int &e=p[x]; while (in[x] + range[e] < cnt - 1) ++e; cnt = in[x] + range[e] + 1; } void Encode(int N, int A[], int B[]) { const double r = 1.055645; //const double r = 1.120438; range.push_back(0); for (int i = 1;i<256; ++i) { int ar = r * range.back(); if (range.back() == ar) ++ar; range.push_back(ar); } for (int i = 0; i < N-1; ++i) { edge[B[i]].push_back(A[i]); edge[A[i]].push_back(B[i]); } dfs(0,-1); for (int i = 0; i < N ; ++i) Code(i, in[i] + (p[i] << 20)); }
#include "Device.h" #include <vector> using namespace std; vector<int> a; void InitDevice() { const double r = 1.055645; a.push_back(0); for (int i = 1; i < 256; ++i) { int ar = a.back()*r; if (a.back() == ar)++ar; a.push_back(ar); } } int Answer(long long S, long long T) { int ss = S & ((1 << 20) - 1); int ts= T & ((1 << 20) - 1); int se = ss+a[S >> 20]; int te = ts+a[T >> 20]; if (ss <= ts && te <= se) return 1; if (ts <= ss && se <= te) return 0; return 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...