#include<bits/stdc++.h>
#include "Ali.h"
#define MAXN 20007
using namespace std;
namespace{
int n,xx,yy,k,root;
const int bucket=7;
vector<int> v[MAXN];
int dist[MAXN],where[MAXN],num[MAXN],cnt[MAXN];
int l,r,mins,currdist;
vector<int> code[MAXN],nodes[MAXN];
void reset(){
k=0; mins=n+1;
for(int i=0;i<n;i++){
v[i].clear(); code[i].clear();
nodes[i].clear();
cnt[i]=0;
}
}
vector<int> dfs(int x,int p){
vector<int> comp={x},curr;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
curr=dfs(v[x][i],x);
for(int f:curr)comp.push_back(f);
}
if(comp.size()>=bucket or p==-1){
for(int f:comp)where[f]=k;
nodes[k]=comp;
k++; comp.clear();
}
return comp;
}
void dfs2(int x,int p){
num[x]=where[x]*(2*bucket-1)+cnt[where[x]];
SetID(x,num[x]); cnt[where[x]]++;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
if(where[x]==where[v[x][i]]){
code[where[x]].push_back(0);
}
dfs2(v[x][i],x);
}
if(p!=-1 and where[x]==where[p]){
code[where[x]].push_back(1);
}
}
void dfs3(int x,int p,int d){
dist[x]=d;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
dfs3(v[x][i],x,d+1);
}
}
}
vector<int> perm;
void Init(int N, vector<int> U, vector<int> V){
srand(10);
n=N;
reset();
perm={};
for(int i=0;i<n;i++)perm.push_back(i);
for(int i=0;i<n-1;i++){
v[U[i]].push_back(V[i]);
v[V[i]].push_back(U[i]);
}
random_shuffle(perm.begin(),perm.end());
for(int i:perm){
if(v[i].size()<3)root=i;
}
dfs(root,-1);
dfs2(root,-1);
}
string SendA(string S){
xx=yy=0;
for(int i=0;i<20;i++){
xx*=2;
if(S[i]=='1')xx++;
}
int z=0;
for(int i=0;i<=1430;i++){
for(int f=i;f<=1430;f++){
if(z==xx){
xx=i; yy=f;
i=f=2000;
}
z++;
}
}
for(int i:nodes[xx]){
dfs3(i,-1,0);
currdist=n;
for(int f:nodes[yy]){
currdist=min(currdist,dist[f]);
}
if(currdist<mins){
mins=currdist;
l=i;
for(int f:nodes[yy]){
if(dist[f]==mins)r=f;
}
}
}
l=num[l]%(2*bucket-1); r=num[r]%(2*bucket-1);
string res="";
for(int i=0;i<26;i++){
if(i<code[xx].size())res.push_back(code[xx][i]+'0');
else res+="1";
}
for(int i=3;i>=0;i--){
if(((1<<i)&l)==0)res.push_back('0');
else res.push_back('1');
}
for(int i=0;i<26;i++){
if(i<code[yy].size())res.push_back(code[yy][i]+'0');
else res.push_back('1');
}
for(int i=3;i>=0;i--){
if(((1<<i)&r)==0)res.push_back('0');
else res.push_back('1');
}
for(int i=13;i>=0;i--){
if(((1<<i)&mins)==0)res.push_back('0');
else res.push_back('1');
}
return res;
}
#include<bits/stdc++.h>
#include "Benjamin.h"
#define MAXN 20007
using namespace std;
namespace{
int nn,from,to,s,pos,dis,ld,rd,pt,nd;
vector<int> codel,coder;
vector<int> treel[40],treer[40];
int dst[40],as,bs;
const int del=13;
void resets(){
codel.clear(); coder.clear();
for(int i=0;i<40;i++){
treel[i].clear();
treer[i].clear();
dst[i]=0;
}
}
void dfs4(int x){
while(pt<codel.size()){
if(codel[pt]==0){
nd++; pt++;
treel[x].push_back(nd);
treel[nd].push_back(x);
dfs4(nd);
}else{
pt++;
return;
}
}
}
void dfs5(int x){
while(pt<coder.size()){
if(coder[pt]==0){
nd++; pt++;
treer[x].push_back(nd);
treer[nd].push_back(x);
dfs5(nd);
}else{
pt++;
return;
}
}
}
void dfs6(int x,int p,int d){
dst[x]=d;
for(int i=0;i<treel[x].size();i++){
if(treel[x][i]==p)continue;
dfs6(treel[x][i],x,d+1);
}
}
void dfs7(int x,int p,int d){
dst[x]=d;
for(int i=0;i<treer[x].size();i++){
if(treer[x][i]==p)continue;
dfs7(treer[x][i],x,d+1);
}
}
}
string SendB(int N, int X, int Y){
resets();
nn=N; from=X; to=Y;
if(from>to)swap(from,to);
int z=0;
for(int i=0;i<=1430;i++){
for(int f=i;f<=1430;f++){
if(i==from/del and to/del==f){
i=f=2000;
break;
}
z++;
}
}
string res="";
for(int i=19;i>=0;i--){
if((z&(1<<i))==0)res.push_back('0');
else res.push_back('1');
}
return res;
}
int Answer(string T){
pos=ld=rd=0;
for(int i=pos;i<pos+26;i++){
codel.push_back(T[i]-'0');
}
pos+=26;
for(int i=pos;i<pos+4;i++){
ld*=2;
if(T[i]=='1')ld++;
}
pos+=4;
nd=pt=0;
dfs4(0);
if(from/del==to/del){
dfs6(to%del,-1,0);
return dst[from%del];
}
dfs6(ld,-1,0);
as=dst[from%del];
for(int i=pos;i<pos+26;i++){
coder.push_back(T[i]-'0');
}
pos+=26;
for(int i=pos;i<pos+4;i++){
rd*=2;
if(T[i]=='1')rd++;
}
pos+=4;
nd=pt=0;
dfs5(0);
dfs7(rd,-1,0);
bs=dst[to%del];
dis=0;
for(int i=pos;i<pos+14;i++){
dis*=2;
if(T[i]=='1')dis++;
}
return as+dis+bs;
}
Compilation message
Ali.cpp: In function 'std::vector<int> {anonymous}::dfs(int, int)':
Ali.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Ali.cpp: In function 'void {anonymous}::dfs2(int, int)':
Ali.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Ali.cpp: In function 'void {anonymous}::dfs3(int, int, int)':
Ali.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:140:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | if(i<code[xx].size())res.push_back(code[xx][i]+'0');
| ~^~~~~~~~~~~~~~~~
Ali.cpp:150:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | if(i<code[yy].size())res.push_back(code[yy][i]+'0');
| ~^~~~~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs4(int)':
Benjamin.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | while(pt<codel.size()){
| ~~^~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs5(int)':
Benjamin.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while(pt<coder.size()){
| ~~^~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs6(int, int, int)':
Benjamin.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i=0;i<treel[x].size();i++){
| ~^~~~~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs7(int, int, int)':
Benjamin.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<treer[x].size();i++){
| ~^~~~~~~~~~~~~~~~
Benjamin.cpp: At global scope:
Benjamin.cpp:8:20: warning: '{anonymous}::s' defined but not used [-Wunused-variable]
8 | int nn,from,to,s,pos,dis,ld,rd,pt,nd;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2440 KB |
Output is correct |
2 |
Correct |
1 ms |
2436 KB |
Output is correct |
3 |
Correct |
2 ms |
2440 KB |
Output is correct |
4 |
Correct |
1 ms |
2440 KB |
Output is correct |
5 |
Correct |
1 ms |
2436 KB |
Output is correct |
6 |
Correct |
8 ms |
3248 KB |
Output is correct |
7 |
Correct |
8 ms |
3268 KB |
Output is correct |
8 |
Correct |
8 ms |
3268 KB |
Output is correct |
9 |
Correct |
8 ms |
3264 KB |
Output is correct |
10 |
Correct |
15 ms |
3784 KB |
Output is correct |
11 |
Correct |
5 ms |
3104 KB |
Output is correct |
12 |
Correct |
7 ms |
3268 KB |
Output is correct |
13 |
Correct |
6 ms |
3100 KB |
Output is correct |
14 |
Correct |
7 ms |
3296 KB |
Output is correct |
15 |
Correct |
7 ms |
4656 KB |
Output is correct |
16 |
Correct |
8 ms |
3472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
2444 KB |
Output is partially correct |
2 |
Partially correct |
66 ms |
5272 KB |
Output is partially correct |
3 |
Partially correct |
4 ms |
2296 KB |
Output is partially correct |
4 |
Partially correct |
338 ms |
4108 KB |
Output is partially correct |
5 |
Partially correct |
320 ms |
4076 KB |
Output is partially correct |
6 |
Partially correct |
320 ms |
4340 KB |
Output is partially correct |
7 |
Partially correct |
301 ms |
5228 KB |
Output is partially correct |
8 |
Partially correct |
330 ms |
4240 KB |
Output is partially correct |
9 |
Partially correct |
225 ms |
4608 KB |
Output is partially correct |
10 |
Partially correct |
232 ms |
5340 KB |
Output is partially correct |
11 |
Partially correct |
272 ms |
4368 KB |
Output is partially correct |
12 |
Partially correct |
30 ms |
3756 KB |
Output is partially correct |
13 |
Partially correct |
147 ms |
3904 KB |
Output is partially correct |
14 |
Partially correct |
165 ms |
3924 KB |
Output is partially correct |
15 |
Partially correct |
4 ms |
2508 KB |
Output is partially correct |
16 |
Partially correct |
226 ms |
5496 KB |
Output is partially correct |
17 |
Partially correct |
232 ms |
5308 KB |
Output is partially correct |
18 |
Partially correct |
235 ms |
4880 KB |
Output is partially correct |
19 |
Partially correct |
266 ms |
4924 KB |
Output is partially correct |
20 |
Partially correct |
151 ms |
4308 KB |
Output is partially correct |
21 |
Partially correct |
231 ms |
5436 KB |
Output is partially correct |
22 |
Partially correct |
244 ms |
3728 KB |
Output is partially correct |
23 |
Partially correct |
235 ms |
4064 KB |
Output is partially correct |
24 |
Partially correct |
245 ms |
4248 KB |
Output is partially correct |
25 |
Partially correct |
239 ms |
4572 KB |
Output is partially correct |
26 |
Partially correct |
237 ms |
4324 KB |
Output is partially correct |
27 |
Partially correct |
251 ms |
4060 KB |
Output is partially correct |
28 |
Partially correct |
237 ms |
4284 KB |
Output is partially correct |
29 |
Partially correct |
239 ms |
3884 KB |
Output is partially correct |
30 |
Partially correct |
243 ms |
4200 KB |
Output is partially correct |
31 |
Partially correct |
249 ms |
4204 KB |
Output is partially correct |
32 |
Partially correct |
239 ms |
3796 KB |
Output is partially correct |
33 |
Partially correct |
259 ms |
4372 KB |
Output is partially correct |
34 |
Partially correct |
234 ms |
3840 KB |
Output is partially correct |
35 |
Partially correct |
239 ms |
4216 KB |
Output is partially correct |
36 |
Partially correct |
241 ms |
3828 KB |
Output is partially correct |
37 |
Partially correct |
249 ms |
3916 KB |
Output is partially correct |
38 |
Partially correct |
242 ms |
4016 KB |
Output is partially correct |
39 |
Partially correct |
41 ms |
3776 KB |
Output is partially correct |
40 |
Partially correct |
354 ms |
5240 KB |
Output is partially correct |