# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
101121 |
2019-03-16T17:27:34 Z |
gs14004 |
City (JOI17_city) |
C++17 |
|
164 ms |
19504 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
vector<int> generate_seq(){
double rat = 1.05;
vector<int> v = {1};
while(rat < 1e8){
int curV = (int)round(rat);
if(curV != v.back()) v.push_back(curV);
rat *= 1.05;
}
return v;
}
vector<int> seq;
vector<int> gph[MAXN];
int dfn[MAXN], sz[MAXN], piv;
void dfs(int x, int p){
sz[x] = 1;
dfn[x] = ++piv;
for(auto &i : gph[x]){
if(i != p){
dfs(i, x);
sz[x] += sz[i];
}
}
while(!binary_search(seq.begin(), seq.end(), sz[x])){
sz[x]++;
}
}
void Encode(int N, int A[], int B[]){
for(int i=0; i<N-1; i++){
gph[A[i]].push_back(B[i]);
gph[B[i]].push_back(A[i]);
}
seq = generate_seq();
dfs(0, -1);
for (int i = 0; i < N; ++i) {
sz[i] = lower_bound(seq.begin(), seq.end(), sz[i]) - seq.begin();
Code(i, ((long long)dfn[i] << 10) + sz[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define generate_seq fuck
#define seq fuckk
vector<int> generate_seq(){
double rat = 1.05;
vector<int> v = {1};
while(rat < 1e8){
int curV = (int)round(rat);
if(curV != v.back()) v.push_back(curV);
rat *= 1.05;
}
return v;
}
vector<int> seq;
void InitDevice(){
seq = generate_seq();
}
int Answer(long long S, long long T){
int dfnS = (S >> 10);
int szS = S & ((1<<10) - 1);
szS = seq[szS];
int dfnT = (T >> 10);
int szT = T & ((1<<10) - 1);
szT = seq[szT];
if(dfnS <= dfnT && dfnT + szT <= dfnS + szS){
return 1;
}
if(dfnT <= dfnS && dfnS + szS <= dfnT + szT){
return 0;
}
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12544 KB |
Output is correct |
2 |
Correct |
8 ms |
12288 KB |
Output is correct |
3 |
Correct |
8 ms |
12288 KB |
Output is correct |
4 |
Correct |
8 ms |
12288 KB |
Output is correct |
5 |
Correct |
8 ms |
12544 KB |
Output is correct |
6 |
Correct |
8 ms |
12544 KB |
Output is correct |
7 |
Correct |
8 ms |
12544 KB |
Output is correct |
8 |
Correct |
8 ms |
12544 KB |
Output is correct |
9 |
Correct |
8 ms |
12544 KB |
Output is correct |
10 |
Correct |
8 ms |
12544 KB |
Output is correct |
11 |
Correct |
8 ms |
12288 KB |
Output is correct |
12 |
Correct |
8 ms |
12544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
164 ms |
19504 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |