| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 274937 | TMJN | 저장 (Saveit) (IOI10_saveit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
static int d[1000][36];
static bool b[1000][36];
static vector<int>v[1000];
void bfs(int x){
b[x][x]=true;
queue<int>q;
int dis=0;
q.push(x);
q.push(-1);
while(q.size()>=2){
int t=q.front();
q.pop();
if(t==-1){
dis++;
q.push(-1);
continue;
}
if(d[t][x]==-1){
d[t][x]=dis;
for(int i:v[t]){
q.push(i);
}
}
}
}
void send0(int x){
if(x==0){
encode_bit(1);
}
else{
encode_bit(0);
send1(x);
}
}
void send1(int x){
for(int i=9;i>=0;i--){
encode_bit((x>>i)&1);
}
}
void encode(int N, int H, int P, int *A, int *B){
for(int i=0;i<N;i++){
for(int j=0;j<H;j++){
d[i][j]=-1;
b[i][j]=false;
}
}
for(int i=0;i<P;i++){
if(A[i]>B[i])swap(A[i],B[i]);
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
for(int i=0;i<H;i++){
bfs(i);
}
vector<int>r[1000];
priority_queue<pair<int,pair<int,int>>>pq;
for(int i=0;i<P;i++){
int c=0;
for(int j=0;j<H;j++){
if(d[A[i]][j]!=d[B[i]][j])c++;
}
pq.push({c,{A[i],B[i]}});
}
while(!pq.empty()){
auto pp=pq.top();
pq.pop();
bool f=false;
for(int i=0;i<H;i++){
if((d[pp.second.first][i]<d[pp.second.second][i]&&!b[pp.second.second][i])||(d[pp.second.second][i]<d[pp.second.first][i]&&!b[pp.second.first][i])){
f=true;
break;
}
}
if(f){
r[pp.second.first].push_back(pp.second.second);
for(int i=0;i<H;i++){
if(d[pp.second.first][i]<d[pp.second.second][i]){
b[pp.second.second][i]=true;
}
if(d[pp.second.second][i]<d[pp.second.first][i]){
b[pp.second.first][i]=true;
}
}
}
}
for(int i=0;i<N;i++){
send0(r[i].size());
for(int j:r[i]){
send1(j);
}
}
return;
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
static vector<int>v[1000];
static int d[1000][36];
int read0(){
int t=decode_bit();
if(t){
return read1();
}
else return 0;
}
int read1(){
int t=0;
for(int i=9;i>=0;i--){
if(decode_bit()){
t+=(1<<i);
}
}
return t;
}
void bfs(int x){
queue<int>q;
int dis=0;
q.push(x);
q.push(-1);
while(q.size()>=2){
int t=q.front();
q.pop();
if(t==-1){
dis++;
q.push(-1);
continue;
}
if(d[t][x]==-1){
d[t][x]=dis;
for(int i:v[t]){
q.push(i);
}
}
}
}
void decode(int N, int H) {
for(int i=0;i<N;i++){
int t=read0();
for(int j=0;j<t;j++){
int k=read1();
v[i].push_back(k);
v[k].push_back(i);
}
}
for(int i=0;i<N;i++){
for(int j=0;j<H;j++){
d[i][j]=-1;
}
}
for(int i=0;i<H;i++){
bfs(i);
}
for(int i=0;i<N;i++){
for(int j=0;j<H;j++){
hops(j,i,d[i][j]);
}
}
}