Submission #563951

#TimeUsernameProblemLanguageResultExecution timeMemory
563951blueCity (JOI17_city)C++17
46 / 100
434 ms54200 KiB
#include "Encoder.h" #include <vector> #include <algorithm> #include <iostream> #include <set> #include <cassert> using namespace std; namespace{ using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) const int mx = 350'000; using ll = long long; using vll = vector<ll>; int N; vi edge[mx]; vll code(mx, 0); vll dfsind(mx, 0); vll subtree(mx, 1); vll fakesubtree(mx, 1); int ct = -1; vll getsizes() { double base = 1.0001; set<ll> res; double curr = 1; while(res.empty() || *res.rbegin() < mx) { curr *= base; res.insert(curr); } vll resvec; for(ll k : res) resvec.push_back(k); return resvec; } vll sizes; void dfs(int u, int p) { // cerr << "dfs " << u << '\n'; dfsind[u] = ++ct; for(int v : edge[u]) { if(v == p) continue; dfs(v, u); subtree[u] += subtree[v]; } auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]); assert(z != sizes.end() && *z >= subtree[u]); subtree[u] = *z; fakesubtree[u] = z - sizes.begin(); } } void Encode(int N_, int A[], int B[]) { N = N_; sizes = getsizes(); cerr << sz(sizes) << '\n'; // for(int z : sizes) // cerr << z << ' '; // cerr << '\n'; for(int e = 0; e < N-1; e++) { edge[A[e]].push_back(B[e]); edge[B[e]].push_back(A[e]); } // cerr << "done\n"; dfs(0, -1); // cerr << "done2\n"; for(int i = 0; i < N; i++) { // cerr << i << " : " << dfsind[i] << ' ' << subtree[i] << ' ' << ((dfsind[i]<<18) | subtree[i]) << '\n'; Code(i, (fakesubtree[i] << 18) | dfsind[i]); } }
#include "Device.h" #include <vector> #include <algorithm> #include <iostream> #include <set> using namespace std; namespace { using vi = vector<int>; using vvi = vector<vi>; using ll = long long; using vll = vector<ll>; #define sz(x) int(x.size()) const int mx = 350'000; vll getsizes() { double base = 1.0001; set<ll> res; double curr = 1; while(res.empty() || *res.rbegin() < mx) { curr *= base; res.insert(curr); } vll resvec; for(ll k : res) resvec.push_back(k); return resvec; } vll sizes; } void InitDevice() { sizes = getsizes(); } int Answer(long long S, long long T) { ll s_st = sizes[S>>18]; ll s_ind = S & ((1<<18) - 1); ll t_st = sizes[T>>18]; ll t_ind = T & ((1<<18) - 1); // cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n"; if(t_ind <= s_ind && s_ind + s_st <= t_ind + t_st) return 0; else if(s_ind <= t_ind && t_ind + t_st <= s_ind + s_st) return 1; else return 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...