제출 #414818

#제출 시각아이디문제언어결과실행 시간메모리
414818amoo_safarCity (JOI17_city)C++17
97 / 100
613 ms42392 KiB
#include "Encoder.h" #include <bits/stdc++.h> using namespace std; const int N = 30e4; const int bl = 150; const int sd = 58; 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 ++; shuffle(G[u].begin(), G[u].end(), rng); bool fl = true; bool lf = true; for(auto adj : G[u]) if(adj != p) lf = false; for(auto adj : G[u]) if((adj != p) && ((int) G[adj].size() > 1)) fl = false; if((fl) && (!lf)){ for(auto adj : G[u]){ if(adj != p){ st[adj] = T; fn[adj] = T + 1; } } T ++; } else { 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 = 30e4; const int bl = 150; const int sd = 58; 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){ if(S == T) return 2; 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; }

컴파일 시 표준 에러 (stderr) 메시지

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