oj.uz

답안 #271579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271579 2020-08-18T06:48:29 Z 송준혁(#5108) 저장 (Saveit) (IOI10_saveit) C++14
100 / 100
 390 ms 11824 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

static int P[1010], D[1010], T[60606], num;
static bool chk[1010];
static vector<int> adj[1010];

void encode(int N, int H, int M, int *v1, int *v2){
	for (int i=0; i<M; i++) adj[v1[i]].pb(v2[i]), adj[v2[i]].pb(v1[i]);
	queue<int> Q;
	for (int i=0; i<H; i++){
		memset(chk, false, sizeof chk);
		Q.push(i);
		chk[i]=true, D[i]=0;
		while (Q.size()){
			int u=Q.front();
			Q.pop();
			for(int v : adj[u]) if (!chk[v]){
				chk[v]=true;
				if (i==0) P[v]=u;
				D[v]=D[u]+1;
				Q.push(v);
			}
		}
		if (i==0) for (int i=1; i<N; i++) for (int j=0; j<10; j++) encode_bit(!!(P[i]&(1<<j)));
		for (int j=1; j<N; j++) T[++num]=D[P[j]]-D[j]+1;
	}
	for (int i=1; i<=36000; i+=3){
		int x=T[i]+T[i+1]*3+T[i+2]*9;
		for (int j=0; j<5; j++) encode_bit(!!(x&(1<<j)));
	}
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

static int P[1010], T[60606], D[1010], chk[1010];

void decode(int N, int H){
	for (int i=1; i<N; i++) for (int j=0; j<10; j++) P[i] |= decode_bit()<<j;
	for (int i=1; i<=36000; i+=3){
		int x=0;
		for (int j=0; j<5; j++) x |= decode_bit()<<j;
		T[i]=x%3, T[i+1]=(x/3)%3, T[i+2]=x/9;
	}
	for (int i=0; i<H; i++){
		memset(chk, false, sizeof chk);
		chk[i]=true, D[i]=0;
		for (int j=0; j<N; j++) for (int k=1; k<N; k++){
			if (chk[P[k]]) chk[k]=true, D[k]=D[P[k]]-(T[i*(N-1)+k]-1);
			if (chk[k]) chk[P[k]]=true, D[P[k]]=D[k]+(T[i*(N-1)+k]-1);
		}
		for (int j=0; j<N; j++) hops(i, j, D[j]);
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 11824 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 15 ms 5376 KB Output is correct - 60040 call(s) of encode_bit()
3 Correct 132 ms 5760 KB Output is correct - 68990 call(s) of encode_bit()
4 Correct 15 ms 5452 KB Output is correct - 60040 call(s) of encode_bit()
5 Correct 143 ms 6248 KB Output is correct - 68990 call(s) of encode_bit()
6 Correct 160 ms 5996 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 189 ms 6332 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 143 ms 5784 KB Output is correct - 69600 call(s) of encode_bit()
9 Correct 161 ms 5924 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 156 ms 5880 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 174 ms 6048 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 163 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 182 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 159 ms 5836 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 158 ms 5776 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 185 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 171 ms 6312 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 188 ms 6520 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 170 ms 6008 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 200 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 210 ms 6988 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 186 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 294 ms 7160 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 11824 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 15 ms 5376 KB Output is correct - 60040 call(s) of encode_bit()
3 Correct 132 ms 5760 KB Output is correct - 68990 call(s) of encode_bit()
4 Correct 15 ms 5452 KB Output is correct - 60040 call(s) of encode_bit()
5 Correct 143 ms 6248 KB Output is correct - 68990 call(s) of encode_bit()
6 Correct 160 ms 5996 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 189 ms 6332 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 143 ms 5784 KB Output is correct - 69600 call(s) of encode_bit()
9 Correct 161 ms 5924 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 156 ms 5880 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 174 ms 6048 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 163 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 182 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 159 ms 5836 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 158 ms 5776 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 185 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 171 ms 6312 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 188 ms 6520 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 170 ms 6008 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 200 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 210 ms 6988 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 186 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 294 ms 7160 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 11824 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 15 ms 5376 KB Output is correct - 60040 call(s) of encode_bit()
3 Correct 132 ms 5760 KB Output is correct - 68990 call(s) of encode_bit()
4 Correct 15 ms 5452 KB Output is correct - 60040 call(s) of encode_bit()
5 Correct 143 ms 6248 KB Output is correct - 68990 call(s) of encode_bit()
6 Correct 160 ms 5996 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 189 ms 6332 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 143 ms 5784 KB Output is correct - 69600 call(s) of encode_bit()
9 Correct 161 ms 5924 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 156 ms 5880 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 174 ms 6048 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 163 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 182 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 159 ms 5836 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 158 ms 5776 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 185 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 171 ms 6312 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 188 ms 6520 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 170 ms 6008 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 200 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 210 ms 6988 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 186 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 294 ms 7160 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 11824 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 15 ms 5376 KB Output is correct - 60040 call(s) of encode_bit()
3 Correct 132 ms 5760 KB Output is correct - 68990 call(s) of encode_bit()
4 Correct 15 ms 5452 KB Output is correct - 60040 call(s) of encode_bit()
5 Correct 143 ms 6248 KB Output is correct - 68990 call(s) of encode_bit()
6 Correct 160 ms 5996 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 189 ms 6332 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 143 ms 5784 KB Output is correct - 69600 call(s) of encode_bit()
9 Correct 161 ms 5924 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 156 ms 5880 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 174 ms 6048 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 163 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 182 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 159 ms 5836 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 158 ms 5776 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 185 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 171 ms 6312 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 188 ms 6520 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 170 ms 6008 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 200 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 210 ms 6988 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 186 ms 6392 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 294 ms 7160 KB Output is correct - 69990 call(s) of encode_bit()