oj.uz

답안 #520221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520221 2022-01-28T22:31:34 Z new_acc 저장 (Saveit) (IOI10_saveit) C++14
100 / 100
 205 ms 13368 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[40][N];
bool vis[N];
ll pot[40];
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) s[i][j]=2;
			if(odl[j]==odl[oj[j]]) s[i][j]=1;
			if(odl[j]+1==odl[oj[j]]) s[i][j]=0;
		}
	}
	pot[0]=1;
	for(int i=1;i<36;i++) pot[i]=pot[i-1]*3;
	rep(i,n){
		ll ans=0;
		rep(j,h) ans+=pot[j]*s[j][i];
		rep(j,60){
			if((1LL<<j)&ans) encode_bit(1);
			else encode_bit(0);
		}
	}
}
#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[40][N];
bool vis[N];
ll pot[40];
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,n){
		ll ans=0;
		rep(j,60){
			int x=decode_bit();
			if(x==1) ans+=(1LL<<j);
		}
		rep(j,h){
			s[j][i]=ans%3;
			ans/=3;
		}
	}
	rep(i,h){
		deque<int> deq;
		deq.push_back(i);
		rep(j,n) vis[j]=0;
		odl[i]=0,vis[i]=1;
		while(!deq.empty()){
			int v=deq.front();
			deq.pop_front();
			if(vis[oj[v]]){
				if(s[i][v]==2) odl[v]=odl[oj[v]]+1;
				if(s[i][v]==1) odl[v]=odl[oj[v]];
				if(s[i][v]==0) odl[v]=odl[oj[v]]-1;
			}else{
				if(s[i][v]==2) odl[oj[v]]=odl[v]-1;
				if(s[i][v]==1) odl[oj[v]]=odl[v];
				if(s[i][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 205 ms 13368 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 350 call(s) of encode_bit()
3 Correct 23 ms 5636 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 3 ms 4576 KB Output is correct - 350 call(s) of encode_bit()
5 Correct 26 ms 5916 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 27 ms 5916 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 37 ms 6608 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 25 ms 5620 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5776 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 27 ms 5788 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 24 ms 5984 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 20 ms 5716 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 51 ms 6652 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 23 ms 5664 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 20 ms 5860 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 45 ms 6524 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 36 ms 6500 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 47 ms 6932 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 36 ms 6288 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 56 ms 7408 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 64 ms 7608 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 67 ms 6796 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 69 ms 7968 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 13368 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 350 call(s) of encode_bit()
3 Correct 23 ms 5636 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 3 ms 4576 KB Output is correct - 350 call(s) of encode_bit()
5 Correct 26 ms 5916 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 27 ms 5916 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 37 ms 6608 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 25 ms 5620 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5776 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 27 ms 5788 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 24 ms 5984 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 20 ms 5716 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 51 ms 6652 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 23 ms 5664 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 20 ms 5860 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 45 ms 6524 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 36 ms 6500 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 47 ms 6932 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 36 ms 6288 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 56 ms 7408 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 64 ms 7608 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 67 ms 6796 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 69 ms 7968 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 13368 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 350 call(s) of encode_bit()
3 Correct 23 ms 5636 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 3 ms 4576 KB Output is correct - 350 call(s) of encode_bit()
5 Correct 26 ms 5916 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 27 ms 5916 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 37 ms 6608 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 25 ms 5620 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5776 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 27 ms 5788 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 24 ms 5984 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 20 ms 5716 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 51 ms 6652 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 23 ms 5664 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 20 ms 5860 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 45 ms 6524 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 36 ms 6500 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 47 ms 6932 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 36 ms 6288 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 56 ms 7408 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 64 ms 7608 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 67 ms 6796 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 69 ms 7968 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 13368 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 350 call(s) of encode_bit()
3 Correct 23 ms 5636 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 3 ms 4576 KB Output is correct - 350 call(s) of encode_bit()
5 Correct 26 ms 5916 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 27 ms 5916 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 37 ms 6608 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 25 ms 5620 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5776 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 27 ms 5788 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 24 ms 5984 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 20 ms 5716 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 51 ms 6652 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 23 ms 5664 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 20 ms 5860 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 45 ms 6524 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 36 ms 6500 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 47 ms 6932 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 36 ms 6288 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 56 ms 7408 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 64 ms 7608 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 67 ms 6796 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 69 ms 7968 KB Output is correct - 70000 call(s) of encode_bit()