oj.uz

답안 #1019089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019089 2024-07-10T13:17:36 Z socpite 저장 (Saveit) (IOI10_saveit) C++14
50 / 100
 325 ms 15008 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;

namespace {

const int maxn = 1e3+5;

int E[maxn][maxn];
int dist[maxn][maxn];
int vis[maxn];
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
	memset(E, 0, sizeof(E));
	memset(dist, 0, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < ne; i++)E[v1[i]][v2[i]] = E[v2[i]][v1[i]] = 1;
	for(int i = 0; i < nh; i++){
		dist[i][i] = 0;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			auto x = q.front();
			q.pop();
			for(int j = 0; j < nv; j++){
				if(!E[x][j] || dist[i][j] || j == i)continue;
				dist[i][j] = dist[i][x] + 1;
				q.push(j);
			}
		}
	}
	mt19937 rng(69420);
	vector<int> vec(nh);
	iota(vec.begin(), vec.end(), 0);
	shuffle(vec.begin(), vec.end(), rng);
	for(int i = 0; i < nh; i++){
		vis[vec[i]] = 1;
		for(int j = 0; j < nv; j++){
			if(vis[j])continue;
			int mx = nv-1;
			for(int k = 0; k < i; k++){
				mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
			}
			mx--;
			int tmp = dist[vec[i]][j]-1;
			while(mx){
				encode_bit(tmp&1);
				tmp>>=1;
				mx>>=1;
			}
		}
	}
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;

namespace {

const int maxn = 1e3+5;

int dist[maxn][maxn];
int vis[maxn];

}

void decode(int nv, int nh) {
	memset(vis, 0, sizeof(vis));
   	mt19937 rng(69420);
	vector<int> vec(nh);
	iota(vec.begin(), vec.end(), 0);
	shuffle(vec.begin(), vec.end(), rng);
	for(int i = 0; i < nh; i++){
		vis[vec[i]] = 1;
		for(int j = 0; j < nv; j++){
			if(vis[j]){
				hops(vec[i], j, dist[j][vec[i]]);
				continue;
			}
			int mx = nv-1;
			for(int k = 0; k < i; k++){
				mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
			}
			mx--;
			dist[vec[i]][j] = 0;
			int crr = 0;
			while(mx){
				dist[vec[i]][j]|=decode_bit()<<(crr++);
				mx>>=1;
			}
			dist[vec[i]][j]++;
			hops(vec[i], j, dist[vec[i]][j]);
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 14840 KB Output is correct - 46360 call(s) of encode_bit()
2 Correct 4 ms 12580 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 44 ms 13576 KB Output is partially correct - 96909 call(s) of encode_bit()
4 Correct 4 ms 12568 KB Output is correct - 17 call(s) of encode_bit()
5 Correct 48 ms 13620 KB Output is partially correct - 74737 call(s) of encode_bit()
6 Correct 51 ms 13624 KB Output is partially correct - 85018 call(s) of encode_bit()
7 Correct 74 ms 13676 KB Output is partially correct - 76917 call(s) of encode_bit()
8 Correct 54 ms 14184 KB Output is partially correct - 168144 call(s) of encode_bit()
9 Correct 81 ms 14752 KB Output is partially correct - 238575 call(s) of encode_bit()
10 Correct 68 ms 15008 KB Output is partially correct - 238555 call(s) of encode_bit()
11 Correct 80 ms 14496 KB Output is partially correct - 189651 call(s) of encode_bit()
12 Correct 82 ms 15004 KB Output is partially correct - 303839 call(s) of encode_bit()
13 Correct 96 ms 14240 KB Output is partially correct - 144829 call(s) of encode_bit()
14 Correct 71 ms 14768 KB Output is partially correct - 247081 call(s) of encode_bit()
15 Correct 75 ms 14780 KB Output is partially correct - 260859 call(s) of encode_bit()
16 Correct 109 ms 14764 KB Output is partially correct - 220284 call(s) of encode_bit()
17 Correct 99 ms 14704 KB Output is partially correct - 209851 call(s) of encode_bit()
18 Correct 93 ms 14340 KB Output is partially correct - 149983 call(s) of encode_bit()
19 Correct 82 ms 13992 KB Output is partially correct - 142099 call(s) of encode_bit()
20 Correct 105 ms 14092 KB Output is partially correct - 128818 call(s) of encode_bit()
21 Correct 120 ms 14244 KB Output is partially correct - 117244 call(s) of encode_bit()
22 Correct 82 ms 13736 KB Output is partially correct - 85888 call(s) of encode_bit()
23 Correct 120 ms 13988 KB Output is partially correct - 81362 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 14840 KB Output is correct - 46360 call(s) of encode_bit()
2 Correct 4 ms 12580 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 44 ms 13576 KB Output is partially correct - 96909 call(s) of encode_bit()
4 Correct 4 ms 12568 KB Output is correct - 17 call(s) of encode_bit()
5 Correct 48 ms 13620 KB Output is partially correct - 74737 call(s) of encode_bit()
6 Correct 51 ms 13624 KB Output is partially correct - 85018 call(s) of encode_bit()
7 Correct 74 ms 13676 KB Output is partially correct - 76917 call(s) of encode_bit()
8 Correct 54 ms 14184 KB Output is partially correct - 168144 call(s) of encode_bit()
9 Correct 81 ms 14752 KB Output is partially correct - 238575 call(s) of encode_bit()
10 Correct 68 ms 15008 KB Output is partially correct - 238555 call(s) of encode_bit()
11 Correct 80 ms 14496 KB Output is partially correct - 189651 call(s) of encode_bit()
12 Correct 82 ms 15004 KB Output is partially correct - 303839 call(s) of encode_bit()
13 Correct 96 ms 14240 KB Output is partially correct - 144829 call(s) of encode_bit()
14 Correct 71 ms 14768 KB Output is partially correct - 247081 call(s) of encode_bit()
15 Correct 75 ms 14780 KB Output is partially correct - 260859 call(s) of encode_bit()
16 Correct 109 ms 14764 KB Output is partially correct - 220284 call(s) of encode_bit()
17 Correct 99 ms 14704 KB Output is partially correct - 209851 call(s) of encode_bit()
18 Correct 93 ms 14340 KB Output is partially correct - 149983 call(s) of encode_bit()
19 Correct 82 ms 13992 KB Output is partially correct - 142099 call(s) of encode_bit()
20 Correct 105 ms 14092 KB Output is partially correct - 128818 call(s) of encode_bit()
21 Correct 120 ms 14244 KB Output is partially correct - 117244 call(s) of encode_bit()
22 Correct 82 ms 13736 KB Output is partially correct - 85888 call(s) of encode_bit()
23 Correct 120 ms 13988 KB Output is partially correct - 81362 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 14840 KB Output is correct - 46360 call(s) of encode_bit()
2 Correct 4 ms 12580 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 44 ms 13576 KB Output is partially correct - 96909 call(s) of encode_bit()
4 Correct 4 ms 12568 KB Output is correct - 17 call(s) of encode_bit()
5 Correct 48 ms 13620 KB Output is partially correct - 74737 call(s) of encode_bit()
6 Correct 51 ms 13624 KB Output is partially correct - 85018 call(s) of encode_bit()
7 Correct 74 ms 13676 KB Output is partially correct - 76917 call(s) of encode_bit()
8 Correct 54 ms 14184 KB Output is partially correct - 168144 call(s) of encode_bit()
9 Correct 81 ms 14752 KB Output is partially correct - 238575 call(s) of encode_bit()
10 Correct 68 ms 15008 KB Output is partially correct - 238555 call(s) of encode_bit()
11 Correct 80 ms 14496 KB Output is partially correct - 189651 call(s) of encode_bit()
12 Correct 82 ms 15004 KB Output is partially correct - 303839 call(s) of encode_bit()
13 Correct 96 ms 14240 KB Output is partially correct - 144829 call(s) of encode_bit()
14 Correct 71 ms 14768 KB Output is partially correct - 247081 call(s) of encode_bit()
15 Correct 75 ms 14780 KB Output is partially correct - 260859 call(s) of encode_bit()
16 Correct 109 ms 14764 KB Output is partially correct - 220284 call(s) of encode_bit()
17 Correct 99 ms 14704 KB Output is partially correct - 209851 call(s) of encode_bit()
18 Correct 93 ms 14340 KB Output is partially correct - 149983 call(s) of encode_bit()
19 Correct 82 ms 13992 KB Output is partially correct - 142099 call(s) of encode_bit()
20 Correct 105 ms 14092 KB Output is partially correct - 128818 call(s) of encode_bit()
21 Correct 120 ms 14244 KB Output is partially correct - 117244 call(s) of encode_bit()
22 Correct 82 ms 13736 KB Output is partially correct - 85888 call(s) of encode_bit()
23 Correct 120 ms 13988 KB Output is partially correct - 81362 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 14840 KB Output is correct - 46360 call(s) of encode_bit()
2 Correct 4 ms 12580 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 44 ms 13576 KB Output is partially correct - 96909 call(s) of encode_bit()
4 Correct 4 ms 12568 KB Output is correct - 17 call(s) of encode_bit()
5 Correct 48 ms 13620 KB Output is partially correct - 74737 call(s) of encode_bit()
6 Correct 51 ms 13624 KB Output is partially correct - 85018 call(s) of encode_bit()
7 Correct 74 ms 13676 KB Output is partially correct - 76917 call(s) of encode_bit()
8 Correct 54 ms 14184 KB Output is partially correct - 168144 call(s) of encode_bit()
9 Correct 81 ms 14752 KB Output is partially correct - 238575 call(s) of encode_bit()
10 Correct 68 ms 15008 KB Output is partially correct - 238555 call(s) of encode_bit()
11 Correct 80 ms 14496 KB Output is partially correct - 189651 call(s) of encode_bit()
12 Correct 82 ms 15004 KB Output is partially correct - 303839 call(s) of encode_bit()
13 Correct 96 ms 14240 KB Output is partially correct - 144829 call(s) of encode_bit()
14 Correct 71 ms 14768 KB Output is partially correct - 247081 call(s) of encode_bit()
15 Correct 75 ms 14780 KB Output is partially correct - 260859 call(s) of encode_bit()
16 Correct 109 ms 14764 KB Output is partially correct - 220284 call(s) of encode_bit()
17 Correct 99 ms 14704 KB Output is partially correct - 209851 call(s) of encode_bit()
18 Correct 93 ms 14340 KB Output is partially correct - 149983 call(s) of encode_bit()
19 Correct 82 ms 13992 KB Output is partially correct - 142099 call(s) of encode_bit()
20 Correct 105 ms 14092 KB Output is partially correct - 128818 call(s) of encode_bit()
21 Correct 120 ms 14244 KB Output is partially correct - 117244 call(s) of encode_bit()
22 Correct 82 ms 13736 KB Output is partially correct - 85888 call(s) of encode_bit()
23 Correct 120 ms 13988 KB Output is partially correct - 81362 call(s) of encode_bit()