| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 511088 |
2022-01-15T05:48:29 Z |
Register |
City (JOI17_city) |
C++14 |
|
583 ms |
54776 KB |
#include <bits/stdc++.h>
#include "Encoder.h"
using namespace std;
const int N=(1<<18)+10,M=1<<8;
int n,tot,sz[N],dfi[N],dfo[N];
vector<int> e[N];
int id(int x) {return (x-1)/M;}
void dfs0(int x,int fa){
sz[x]=1;
for(int i=0;i<e[x].size();i++) if(e[x][i]==fa) {e[x].erase(e[x].begin()+i);break;}
for(int y:e[x]) dfs0(y,x),sz[x]+=sz[y];
sort(e[x].begin(),e[x].end(),[&](const int&a,const int&b){return sz[a]<sz[b];});
}
void dfs1(int x,int fa){
dfi[x]=++tot;
for(int y:e[x]) dfs1(y,x);
dfo[x]=tot;
if(sz[x]>M){
int k=id(dfo[x]);
Code(x,(1<<27)+M*(k-1)*k/2+dfi[x]);
}
}
void dfs2(int x,int fa,int ri){
if(sz[x]>M) ri=id(dfo[x]);
else Code(x,(ri==id(dfo[x]))<<26|dfi[x]<<8|(sz[x]-1));
for(int y:e[x]) dfs2(y,x,ri);
}
void Encode(int nn,int u[],int v[]){
n=nn;
for(int i=0;i+1<n;i++) e[u[i]].push_back(v[i]),e[v[i]].push_back(u[i]);
dfs0(0,-1);dfs1(0,-1);dfs2(0,-1,0);
}
#include <bits/stdc++.h>
#include "Device.h"
using namespace std;
const int M=256;
void InitDevice(){}
int id(int x) {return (x-1)/M;}
void calc(int&b,int&d,int&k,int x){
if(x>>27&1){
b=1;x-=(1<<27);k=0;
int l=1,r=1000;
while(l<=r){
int mid=l+r>>1;
if(M*mid*(mid-1)/2<x) k=mid,l=mid+1;
else r=mid-1;
}
d=x-M*k*(k-1)/2;
}else b=0,d=(x>>8),k=x-(d<<8);
}
int Answer(long long x,long long y){
int s=x,t=y,bs,ds,ks,bt,dt,kt;
calc(bs,ds,ks,s);calc(bt,dt,kt,t);
if(bs&&bt){
if(ds<dt&&kt<=ks) return 1;
else if(dt<ds&&ks<=kt) return 0;
return 2;
}else if(!bs&&!bt){
if(ds>>18&1) ds-=(1<<18);
if(dt>>18&1) dt-=(1<<18);
int rs=ds+ks,rt=dt+kt;
if(ds<dt&&rt<=rs) return 1;
else if(dt<ds&&rs<=rt) return 0;
return 2;
}else{
bool fl=1,ri=0;
if(bt) swap(ds,dt),swap(ks,kt),fl=0;
if(dt>>18&1) ri=1,dt-=(1<<18);
if(ds>dt||ks<id(dt+kt)) return 2;
if(ks>id(dt+kt)||ri) return fl;
return 2;
}
}
Compilation message
Encoder.cpp: In function 'void dfs0(int, int)':
Encoder.cpp:10:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i=0;i<e[x].size();i++) if(e[x][i]==fa) {e[x].erase(e[x].begin()+i);break;}
| ~^~~~~~~~~~~~
Device.cpp: In function 'void calc(int&, int&, int&, int)':
Device.cpp:12:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6788 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6848 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6792 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6784 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6796 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6752 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6664 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6704 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6680 KB |
Output is correct |
| 11 |
Correct |
5 ms |
6768 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
248 ms |
15928 KB |
Output is correct - L = 134218133 |
| 2 |
Correct |
248 ms |
22160 KB |
Output is correct - L = 134218351 |
| 3 |
Correct |
184 ms |
22204 KB |
Output is correct - L = 134218396 |
| 4 |
Correct |
178 ms |
22204 KB |
Output is correct - L = 134218241 |
| 5 |
Correct |
513 ms |
53800 KB |
Output is correct - L = 256272268 |
| 6 |
Correct |
542 ms |
53756 KB |
Output is correct - L = 256272260 |
| 7 |
Correct |
504 ms |
53684 KB |
Output is correct - L = 256272057 |
| 8 |
Correct |
462 ms |
53604 KB |
Output is correct - L = 256272018 |
| 9 |
Correct |
489 ms |
54608 KB |
Output is correct - L = 256047755 |
| 10 |
Correct |
370 ms |
54760 KB |
Output is correct - L = 256024992 |
| 11 |
Correct |
366 ms |
54776 KB |
Output is correct - L = 256022805 |
| 12 |
Correct |
400 ms |
54724 KB |
Output is correct - L = 256022575 |
| 13 |
Correct |
393 ms |
54364 KB |
Output is correct - L = 256147739 |
| 14 |
Correct |
438 ms |
53964 KB |
Output is correct - L = 256222356 |
| 15 |
Correct |
169 ms |
22344 KB |
Output is correct - L = 134218358 |
| 16 |
Correct |
179 ms |
22212 KB |
Output is correct - L = 134218355 |
| 17 |
Correct |
228 ms |
22228 KB |
Output is correct - L = 134218250 |
| 18 |
Correct |
483 ms |
53936 KB |
Output is correct - L = 256022589 |
| 19 |
Correct |
410 ms |
53952 KB |
Output is correct - L = 256022546 |
| 20 |
Correct |
421 ms |
53856 KB |
Output is correct - L = 256022545 |
| 21 |
Correct |
440 ms |
53864 KB |
Output is correct - L = 256034520 |
| 22 |
Correct |
452 ms |
54044 KB |
Output is correct - L = 256270413 |
| 23 |
Correct |
505 ms |
54036 KB |
Output is correct - L = 256270384 |
| 24 |
Correct |
522 ms |
54028 KB |
Output is correct - L = 256271335 |
| 25 |
Correct |
483 ms |
53888 KB |
Output is correct - L = 256271727 |
| 26 |
Correct |
583 ms |
54060 KB |
Output is correct - L = 256271932 |
| 27 |
Correct |
504 ms |
53896 KB |
Output is correct - L = 256272202 |
