oj.uz

답안 #601088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601088 2022-07-21T11:01:35 Z l_reho 저장 (Saveit) (IOI10_saveit) C++14
50 / 100
 300 ms 16356 KB 
#include "grader.h"
#include "encoder.h"

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

vector<vector<int>> dist;
vector<vector<int>> graph;

struct info{
	int d;
	int node;
	
	bool operator< (const info& rhs) const {
        return d > rhs.d;
    }
	
};

void solver(int hub){
	
	queue<info> q;
	
	q.push({0, hub});
	dist[hub][hub] = 0;
	
	while(!q.empty()){
		info i = q.front();
		q.pop();
		
		int node = i.node;
		int d = i.d;
		
		vector<int> adj = graph[node];
		
		for(int a : adj){
			if(dist[hub][a] != INT_MAX) continue;
			dist[hub][a] = d+1;
			q.push({d+1, a});
		}
		
	}
	
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  // per ogni hub calcolo la distanza da ogni altro hub
	dist.assign(nv, vector<int>(nv, INT_MAX));
	graph.assign(nv, vector<int>());

	for(int i = 0; i < ne; i++){
		graph[v1[i]].push_back(v2[i]);
		graph[v2[i]].push_back(v1[i]);
	}
	
	for(int i = 0; i < nh; i++)
		solver(i);
	
	
	// adesso gli invio le informazioni
	
	for(int h = 0; h < nh; h++){
		for(int v = 0; v < nv; v++){
			
			// faccio l'encode di dist[h][v]
			string bts = "";
			
			while(dist[h][v]){
				// 11 bit
				char c = (dist[h][v] & 1) + '0';
				bts =  c + bts;
				dist[h][v] >>= 1;
			}
			bts = string(10-bts.length(), '0') + bts;
			// cout<<"DEBUG-->"<<bts.length()<<endl;
			for(char c : bts)
				encode_bit(c-'0');
		}
	}
  
	return;
}

#include "grader.h"
#include "decoder.h"

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

void decode(int nv, int nh) {
	
	/*
   int a = decode_bit();
   int b = decode_bit();
   hops(0,0,0);
   hops(1,2,3);
   * */
   
   
	for(int h = 0; h < nh; h++){
		for(int v = 0; v < nv; v++){
			
			int d = 0;
			for(int i = 9; i >= 0; i--){
				int b = decode_bit();
				// cout<<"DEBUG-->"<<h<<" "<<v<<" "<<b<<endl;
				if(b) d += (1<<i);
			}
			
			
			hops(h, v, d);
			// decodifico e invio
			
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 16356 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 70 ms 10532 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 76 ms 10688 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 81 ms 11652 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 119 ms 11980 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 71 ms 11160 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 77 ms 11536 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11556 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 84 ms 11644 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 81 ms 11504 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 110 ms 12232 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 100 ms 11696 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 115 ms 11544 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 12012 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 108 ms 12052 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 152 ms 12316 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 90 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 129 ms 12556 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 145 ms 12688 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 129 ms 12188 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 136 ms 12888 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 16356 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 70 ms 10532 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 76 ms 10688 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 81 ms 11652 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 119 ms 11980 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 71 ms 11160 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 77 ms 11536 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11556 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 84 ms 11644 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 81 ms 11504 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 110 ms 12232 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 100 ms 11696 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 115 ms 11544 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 12012 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 108 ms 12052 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 152 ms 12316 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 90 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 129 ms 12556 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 145 ms 12688 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 129 ms 12188 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 136 ms 12888 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 16356 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 70 ms 10532 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 76 ms 10688 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 81 ms 11652 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 119 ms 11980 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 71 ms 11160 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 77 ms 11536 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11556 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 84 ms 11644 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 81 ms 11504 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 110 ms 12232 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 100 ms 11696 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 115 ms 11544 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 12012 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 108 ms 12052 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 152 ms 12316 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 90 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 129 ms 12556 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 145 ms 12688 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 129 ms 12188 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 136 ms 12888 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 16356 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 70 ms 10532 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 76 ms 10688 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 81 ms 11652 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 119 ms 11980 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 71 ms 11160 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 77 ms 11536 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11556 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 84 ms 11644 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 81 ms 11504 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 110 ms 12232 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 100 ms 11696 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 115 ms 11544 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 12012 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 108 ms 12052 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 152 ms 12316 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 90 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 129 ms 12556 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 145 ms 12688 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 129 ms 12188 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 136 ms 12888 KB Output is partially correct - 360000 call(s) of encode_bit()