| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 520217 |
2022-01-28T21:38:25 Z |
new_acc |
Saveit (IOI10_saveit) |
C++14 |
|
222 ms |
13220 KB |
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.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];
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 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[u]==-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);
}
}
}
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.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];
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]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
13220 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
4588 KB |
Output is correct - 80 call(s) of encode_bit() |
| 3 |
Correct |
22 ms |
5480 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4580 KB |
Output is correct - 100 call(s) of encode_bit() |
| 5 |
Correct |
25 ms |
5736 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 6 |
Correct |
27 ms |
5776 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 7 |
Correct |
48 ms |
6364 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5500 KB |
Output is partially correct - 78802 call(s) of encode_bit() |
| 9 |
Correct |
24 ms |
5476 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 10 |
Correct |
25 ms |
5488 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 11 |
Correct |
39 ms |
5668 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 12 |
Correct |
22 ms |
5484 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 13 |
Correct |
60 ms |
6604 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 14 |
Correct |
25 ms |
5496 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 15 |
Correct |
28 ms |
5632 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 16 |
Correct |
63 ms |
6288 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 17 |
Correct |
43 ms |
6224 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
6708 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 19 |
Correct |
40 ms |
6100 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 20 |
Correct |
62 ms |
7184 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 21 |
Correct |
90 ms |
7320 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 22 |
Correct |
55 ms |
6556 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 23 |
Correct |
89 ms |
7772 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
13220 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
4588 KB |
Output is correct - 80 call(s) of encode_bit() |
| 3 |
Correct |
22 ms |
5480 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4580 KB |
Output is correct - 100 call(s) of encode_bit() |
| 5 |
Correct |
25 ms |
5736 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 6 |
Correct |
27 ms |
5776 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 7 |
Correct |
48 ms |
6364 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5500 KB |
Output is partially correct - 78802 call(s) of encode_bit() |
| 9 |
Correct |
24 ms |
5476 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 10 |
Correct |
25 ms |
5488 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 11 |
Correct |
39 ms |
5668 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 12 |
Correct |
22 ms |
5484 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 13 |
Correct |
60 ms |
6604 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 14 |
Correct |
25 ms |
5496 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 15 |
Correct |
28 ms |
5632 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 16 |
Correct |
63 ms |
6288 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 17 |
Correct |
43 ms |
6224 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
6708 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 19 |
Correct |
40 ms |
6100 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 20 |
Correct |
62 ms |
7184 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 21 |
Correct |
90 ms |
7320 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 22 |
Correct |
55 ms |
6556 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 23 |
Correct |
89 ms |
7772 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
13220 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
4588 KB |
Output is correct - 80 call(s) of encode_bit() |
| 3 |
Correct |
22 ms |
5480 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4580 KB |
Output is correct - 100 call(s) of encode_bit() |
| 5 |
Correct |
25 ms |
5736 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 6 |
Correct |
27 ms |
5776 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 7 |
Correct |
48 ms |
6364 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5500 KB |
Output is partially correct - 78802 call(s) of encode_bit() |
| 9 |
Correct |
24 ms |
5476 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 10 |
Correct |
25 ms |
5488 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 11 |
Correct |
39 ms |
5668 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 12 |
Correct |
22 ms |
5484 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 13 |
Correct |
60 ms |
6604 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 14 |
Correct |
25 ms |
5496 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 15 |
Correct |
28 ms |
5632 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 16 |
Correct |
63 ms |
6288 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 17 |
Correct |
43 ms |
6224 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
6708 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 19 |
Correct |
40 ms |
6100 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 20 |
Correct |
62 ms |
7184 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 21 |
Correct |
90 ms |
7320 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 22 |
Correct |
55 ms |
6556 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 23 |
Correct |
89 ms |
7772 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
13220 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
4588 KB |
Output is correct - 80 call(s) of encode_bit() |
| 3 |
Correct |
22 ms |
5480 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4580 KB |
Output is correct - 100 call(s) of encode_bit() |
| 5 |
Correct |
25 ms |
5736 KB |
Output is partially correct - 73800 call(s) of encode_bit() |
| 6 |
Correct |
27 ms |
5776 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 7 |
Correct |
48 ms |
6364 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5500 KB |
Output is partially correct - 78802 call(s) of encode_bit() |
| 9 |
Correct |
24 ms |
5476 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 10 |
Correct |
25 ms |
5488 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 11 |
Correct |
39 ms |
5668 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 12 |
Correct |
22 ms |
5484 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 13 |
Correct |
60 ms |
6604 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 14 |
Correct |
25 ms |
5496 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 15 |
Correct |
28 ms |
5632 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 16 |
Correct |
63 ms |
6288 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 17 |
Correct |
43 ms |
6224 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
6708 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 19 |
Correct |
40 ms |
6100 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 20 |
Correct |
62 ms |
7184 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 21 |
Correct |
90 ms |
7320 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 22 |
Correct |
55 ms |
6556 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
| 23 |
Correct |
89 ms |
7772 KB |
Output is partially correct - 82000 call(s) of encode_bit() |
