| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 520213 |
2022-01-28T21:13:34 Z |
new_acc |
Saveit (IOI10_saveit) |
C++14 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=1e3+10;
vi graf[N];
int odl[N],oj[N];
int s[N];
bool vis[N];
string ss="";
int wsk;
/*void encode_bit(int x){
ss+=char(x+48);
}
int decode_bit(){
return int(ss[wsk++])-48;
}*/
void dfs(int v,int o){
vis[v]=1;
oj[v]=o;
for(auto u:graf[v]){
if(vis[u]) continue;
dfs(u,v);
}
}
/*void hops(int h,int c,int d){
cout<<h<<" "<<c<<" "<<d<<"\n";
}*/
void bfs(int x,int n){
rep(i,n) odl[i]=-1;
deque<int> deq;
odl[x]=0;
deq.push_back(x);
while(!deq.empty()){
int v=deq.front();
deq.pop_front();
for(auto u:graf[v]) if(odl[v]==-1) deq.push_back(u),odl[u]=odl[v]+1;
}
}
void encode(int n,int h,int p,int a[],int b[]){
rep(i,p) graf[a[i]].push_back(b[i]),graf[b[i]].push_back(a[i]);
dfs(0,0);
rep(i,n){
rep(j,10){
if(oj[i]&(1<<j)) encode_bit(1);
else encode_bit(0);
}
}
rep(i,h){
bfs(i,n);
rep(j,n){
if(odl[j]==odl[oj[j]]+1) encode_bit(0),encode_bit(0);
if(odl[j]==odl[oj[j]]) encode_bit(0),encode_bit(1);
if(odl[j]+1==odl[oj[j]]) encode_bit(1),encode_bit(1);
}
}
}
void decode(int n,int h){
rep(i,n) graf[i].clear();
rep(i,n){
int x=0;
rep(j,10){
int xd=decode_bit();
if(xd==1) x+=(1<<j);
}
graf[i].push_back(x),graf[x].push_back(i);
oj[i]=x;
}
rep(i,h){
deque<int> deq;
deq.push_back(i);
rep(j,n) vis[j]=0;
odl[i]=0,vis[i]=1;
rep(j,n){
bool xd=decode_bit(),xd2=decode_bit();
if(!xd and !xd2) s[j]=3;
if(!xd and xd2) s[j]=1;
if(xd and xd2) s[j]=0;
}
while(!deq.empty()){
int v=deq.front();
deq.pop_front();
if(vis[oj[v]]){
if(s[v]==3) odl[v]=odl[oj[v]]-1;
if(s[v]==1) odl[v]=odl[oj[v]];
if(s[v]==0) odl[v]=odl[oj[v]]+1;
}else{
if(s[v]==3) odl[oj[v]]=odl[v]+1;
if(s[v]==1) odl[oj[v]]=odl[v];
if(s[v]==0) odl[oj[v]]=odl[v]-1;
}
for(auto u:graf[v]) if(!vis[u]) deq.push_back(u),vis[u]=1;
}
rep(j,n) hops(i,j,odl[j]);
}
}
/*int main(){
int n=5,h=3,p=7;
int a[7],b[7];
a[0]=0,b[0]=2;
a[1]=2,b[1]=1;
a[2]=0,b[2]=1;
a[3]=1,b[3]=3;
a[4]=0,b[4]=3;
a[5]=1,b[5]=4;
a[6]=0,b[6]=4;
encode(n,h,p,a,b);
decode(n,h);
}*/
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:49:21: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
49 | if(oj[i]&(1<<j)) encode_bit(1);
| ^~~~~~~~~~
| encode
encoder.cpp:50:9: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
50 | else encode_bit(0);
| ^~~~~~~~~~
| encode
encoder.cpp:56:29: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
56 | if(odl[j]==odl[oj[j]]+1) encode_bit(0),encode_bit(0);
| ^~~~~~~~~~
| encode
encoder.cpp:57:27: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
57 | if(odl[j]==odl[oj[j]]) encode_bit(0),encode_bit(1);
| ^~~~~~~~~~
| encode
encoder.cpp:58:29: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
58 | if(odl[j]+1==odl[oj[j]]) encode_bit(1),encode_bit(1);
| ^~~~~~~~~~
| encode
encoder.cpp: In function 'void decode(int, int)':
encoder.cpp:67:11: error: 'decode_bit' was not declared in this scope; did you mean 'decode'?
67 | int xd=decode_bit();
| ^~~~~~~~~~
| decode
encoder.cpp:79:12: error: 'decode_bit' was not declared in this scope; did you mean 'decode'?
79 | bool xd=decode_bit(),xd2=decode_bit();
| ^~~~~~~~~~
| decode
encoder.cpp:80:16: error: 'xd2' was not declared in this scope; did you mean 'xd'?
80 | if(!xd and !xd2) s[j]=3;
| ^~~
| xd
encoder.cpp:81:15: error: 'xd2' was not declared in this scope; did you mean 'xd'?
81 | if(!xd and xd2) s[j]=1;
| ^~~
| xd
encoder.cpp:82:14: error: 'xd2' was not declared in this scope; did you mean 'xd'?
82 | if(xd and xd2) s[j]=0;
| ^~~
| xd
encoder.cpp:98:12: error: 'hops' was not declared in this scope
98 | rep(j,n) hops(i,j,odl[j]);
| ^~~~
/usr/bin/ld: /tmp/ccIKpBj9.o: in function `main':
grader_decoder.c:(.text.startup+0x126): undefined reference to `decode(int, int)'
collect2: error: ld returned 1 exit status
