oj.uz

답안 #520217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520217 2022-01-28T21:38:25 Z new_acc 저장 (Saveit) (IOI10_saveit) C++14
50 / 100
 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]);
  }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 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()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 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()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 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()