| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71934 |
2018-08-26T01:24:17 Z |
IvanC |
City (JOI17_city) |
C++17 |
|
618 ms |
82240 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250010;
typedef long long ll;
typedef pair<int,int> ii;
static vector<ii> guloso[MAXN];
static vector<int> grafo[MAXN];
static int tam[MAXN],ini[MAXN],fim[MAXN],dfsCount;
static void dfs_sz(int v,int p){
tam[v] = 1;
int tem_folha = 0;
for(int u : grafo[v]){
if(u == p) continue;
dfs_sz(u,v);
if(tam[u] != 1){
tam[v] += tam[u];
}
else{
if(!tem_folha){
tem_folha = 1;
tam[v] += 1;
}
}
}
}
static void dfs_euler(int v,int p){
ini[v] = ++dfsCount;
int tem_folha = 0;
for(int u : grafo[v]){
if(u == p) continue;
guloso[v].push_back(ii(tam[u],u));
}
sort(guloso[v].rbegin(),guloso[v].rend());
for(ii par : guloso[v]){
int sz_u = par.first, u = par.second;
if(sz_u != 1){
dfs_euler(u,v);
}
else{
if(!tem_folha){
tem_folha++;
dfsCount++;
ini[u] = dfsCount;
fim[u] = dfsCount;
}
else{
ini[u] = dfsCount;
fim[u] = dfsCount;
}
}
}
fim[v] = dfsCount;
}
static long long coding1(int A,int B){
B -= A;
long long davez = A;
davez += (1LL << 18)*ll(B);
return (davez << 1);
}
static long long coding2(int A,int B){
B -= A;
swap(A,B);
long long davez = A;
davez += (1LL << 18)*ll(B);
return (davez << 1) | 1;
}
void Encode(int N, int A[], int B[]){
for(int i = 0;i<N-1;i++){
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
dfs_sz(0,-1);
dfs_euler(0,-1);
for(int i = 0;i<N;i++){
ini[i]--;
fim[i]--;
}
for (int i = 0; i < N; ++i) {
Code(i, min(coding1(ini[i],fim[i]), coding2(ini[i],fim[i]) ) );
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice(){
}
static void Magic(long long X, int &ini, int& fim ){
ini = 0;
fim = 0;
long long flag = (X & 1);
X >>= 1;
long long temp = (X >> 18);
fim += temp;
X -= (temp)*(1 << 18);
ini += X;
if(flag) swap(ini,fim);
fim += ini;
}
int Answer(long long S, long long T){
if(S == T) return 2;
int inia,fima,inib,fimb;
Magic(S,inia,fima);
Magic(T,inib,fimb);
if(inia <= inib && inib <= fima) return 1;
if(inib <= inia && inia <= fimb) return 0;
return 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
24064 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24064 KB |
Output is correct |
| 3 |
Correct |
13 ms |
24064 KB |
Output is correct |
| 4 |
Correct |
13 ms |
24320 KB |
Output is correct |
| 5 |
Correct |
13 ms |
24152 KB |
Output is correct |
| 6 |
Correct |
13 ms |
24064 KB |
Output is correct |
| 7 |
Correct |
13 ms |
24064 KB |
Output is correct |
| 8 |
Correct |
13 ms |
24064 KB |
Output is correct |
| 9 |
Correct |
13 ms |
24320 KB |
Output is correct |
| 10 |
Correct |
12 ms |
24064 KB |
Output is correct |
| 11 |
Correct |
13 ms |
24320 KB |
Output is correct |
| 12 |
Correct |
13 ms |
24064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
31216 KB |
Output is correct - L = 81265048 |
| 2 |
Correct |
174 ms |
31512 KB |
Output is correct - L = 58196568 |
| 3 |
Correct |
175 ms |
31304 KB |
Output is correct - L = 114295286 |
| 4 |
Correct |
176 ms |
31216 KB |
Output is correct - L = 99615390 |
| 5 |
Partially correct |
530 ms |
78272 KB |
Output is partially correct - L = 30857233936 |
| 6 |
Partially correct |
546 ms |
78512 KB |
Output is partially correct - L = 51686098936 |
| 7 |
Partially correct |
519 ms |
78192 KB |
Output is partially correct - L = 26961151386 |
| 8 |
Partially correct |
540 ms |
76264 KB |
Output is partially correct - L = 46764589056 |
| 9 |
Partially correct |
442 ms |
74776 KB |
Output is partially correct - L = 1015036996 |
| 10 |
Correct |
438 ms |
74448 KB |
Output is correct - L = 175113180 |
| 11 |
Correct |
445 ms |
74520 KB |
Output is correct - L = 27787552 |
| 12 |
Correct |
418 ms |
74568 KB |
Output is correct - L = 6291485 |
| 13 |
Partially correct |
473 ms |
76184 KB |
Output is partially correct - L = 13324355732 |
| 14 |
Partially correct |
513 ms |
77456 KB |
Output is partially correct - L = 13458585912 |
| 15 |
Correct |
170 ms |
31216 KB |
Output is correct - L = 48235062 |
| 16 |
Correct |
173 ms |
31216 KB |
Output is correct - L = 132121160 |
| 17 |
Correct |
176 ms |
31248 KB |
Output is correct - L = 82313966 |
| 18 |
Correct |
487 ms |
78728 KB |
Output is correct - L = 8862525 |
| 19 |
Correct |
511 ms |
79040 KB |
Output is correct - L = 8886061 |
| 20 |
Correct |
497 ms |
79056 KB |
Output is correct - L = 8888341 |
| 21 |
Partially correct |
508 ms |
77088 KB |
Output is partially correct - L = 1007497564 |
| 22 |
Correct |
552 ms |
80088 KB |
Output is correct - L = 8587521 |
| 23 |
Correct |
561 ms |
80432 KB |
Output is correct - L = 8586113 |
| 24 |
Correct |
565 ms |
80872 KB |
Output is correct - L = 8498545 |
| 25 |
Correct |
560 ms |
81216 KB |
Output is correct - L = 8459669 |
| 26 |
Correct |
587 ms |
81888 KB |
Output is correct - L = 8438629 |
| 27 |
Correct |
618 ms |
82240 KB |
Output is correct - L = 8417037 |
