Submission #414785

#TimeUsernameProblemLanguageResultExecution timeMemory
414785amoo_safarCity (JOI17_city)C++17
8 / 100
209 ms17164 KiB
#include "Encoder.h" #include <bits/stdc++.h> using namespace std; const int N = 29e4; const int bl = 125; const int sd = 8585; int mk[N]; mt19937 rng(sd); vector<int> V; vector<int> G[N]; int st[N], fn[N], T = 0; void DFS(int u, int p){ st[u] = T ++; for(auto adj : G[u]) if(adj != p) DFS(adj, u); fn[u] = T; while(mk[fn[u] - st[u] ] == -1){ fn[u] ++; // T ++; } // cerr << "!! " << u << ' ' << st[u] << ' ' << fn[u] << '\n'; } void Encode(int _n, int A[], int B[]){ memset(mk, -1, sizeof mk); int cnt = 0; for(int i = 1; i < N; i++){ int pr = (i + bl - 1) / bl; // if(i > N / 2) pr += pr; uniform_int_distribution<> Amoo(1, pr); if(Amoo(rng) == 1){ mk[i] = V.size(); V.push_back(i); } } int sz = V.size(); for(int i = 0; i < _n - 1; i++) G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]); T = 0; DFS(0, -1); cerr << "! " << V.size() << '\n'; // for(int i = 0; i < _n; i++) // cerr << "! " << st[i] << ' ' << fn[i] << '\n'; for(int i = 0; i < _n; i++){ Code(i, 1ll * sz * st[i] + mk[fn[i] - st[i]]); } }
#include "Device.h" #include <bits/stdc++.h> using namespace std; const int N = 29e4; const int bl = 125; const int sd = 8585; mt19937 rng2(sd); vector<int> V2; void InitDevice(){ for(int i = 1; i < N; i++){ int pr = (i + bl - 1) / bl; uniform_int_distribution<> Amoo(1, pr); if(Amoo(rng2) == 1) V2.push_back(i); } } int Answer(long long S, long long T){ int sz = V2.size(); int s1 = S / sz, f1 = s1 + V2[S % sz]; int s2 = T / sz, f2 = s2 + V2[T % sz]; if(s2 <= s1 && s1 < f2) return 0; if(s1 <= s2 && s2 < f1) return 1; return 2; }

Compilation message (stderr)

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:33:6: warning: unused variable 'cnt' [-Wunused-variable]
   33 |  int cnt = 0;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...