oj.uz

Submission #476470

# Submission time Handle Problem Language Result Execution time Memory
476470 2021-09-27T09:35:07 Z AdamGS Saveit (IOI10_saveit) C++14
25 / 100
 324 ms 16564 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
void encode(int n, int h, int m, int *a, int *b) {
	vector<pair<int,int>>V[n];
	int uzyte[m], odl[n];
	rep(i, m) {
		uzyte[i]=0;
		V[a[i]].pb({b[i], i});
		V[b[i]].pb({a[i], i});
	}
	rep(i, h) {
		rep(j, n) odl[j]=1000000007;
		queue<int>q;
		q.push(i);
		odl[i]=0;
		while(!q.empty()) {
			int p=q.front(); q.pop();
			for(auto j : V[p]) if(odl[j.st]>odl[p]+1) {
				odl[j.st]=odl[p]+1;
				q.push(j.st);
				uzyte[j.nd]=1;
			}
		}
	}
	vector<int>T[n];
	rep(i, m) if(uzyte[i]) {
		T[a[i]].pb(b[i]);
		T[b[i]].pb(a[i]);
	}
	rep(i, n) {
		rep(j, 10) encode_bit((T[i].size()&(1<<j))>0);
		for(auto j : T[i]) {
			rep(l, 10) encode_bit((j&(1<<l))>0);
		}
	}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
void decode(int n, int h) {
	vector<int>V[n];
	rep(i, n) {
		int a=0;
		rep(j, 10) a+=decode_bit()*(1<<j);
		rep(j, a) {
			int x=0;
			rep(l, 10) x+=decode_bit()*(1<<l);
			V[i].pb(x);
		}
	}
	rep(i, h) {
		int odl[n];
		rep(j, n) odl[j]=1000000007;
		queue<int>q;
		q.push(i);
		odl[i]=0;
		while(!q.empty()) {
			int p=q.front(); q.pop();
			for(auto j : V[p]) if(odl[j]>odl[p]+1) {
				odl[j]=odl[p]+1;
				q.push(j);
			}
		}
		rep(j, n) hops(i, j, odl[j]);
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16564 KB Output is partially correct - 364600 call(s) of encode_bit()
2 Correct 3 ms 4452 KB Output is correct - 190 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is partially correct - 78680 call(s) of encode_bit()
4 Correct 3 ms 4552 KB Output is correct - 230 call(s) of encode_bit()
5 Correct 50 ms 6888 KB Output is partially correct - 192840 call(s) of encode_bit()
6 Correct 51 ms 6844 KB Output is partially correct - 198280 call(s) of encode_bit()
7 Correct 110 ms 9064 KB Output is partially correct - 372000 call(s) of encode_bit()
8 Correct 24 ms 5156 KB Output is correct - 46130 call(s) of encode_bit()
9 Correct 20 ms 5312 KB Output is correct - 51020 call(s) of encode_bit()
10 Correct 26 ms 5344 KB Output is correct - 48940 call(s) of encode_bit()
11 Correct 44 ms 6084 KB Output is partially correct - 104700 call(s) of encode_bit()
12 Correct 18 ms 5040 KB Output is correct - 29980 call(s) of encode_bit()
13 Correct 98 ms 8224 KB Output is partially correct - 251560 call(s) of encode_bit()
14 Correct 35 ms 5328 KB Output is correct - 55440 call(s) of encode_bit()
15 Correct 33 ms 5536 KB Output is correct - 58540 call(s) of encode_bit()
16 Correct 78 ms 6740 KB Output is partially correct - 117020 call(s) of encode_bit()
17 Correct 73 ms 6532 KB Output is partially correct - 109220 call(s) of encode_bit()
18 Correct 86 ms 7576 KB Output is partially correct - 172320 call(s) of encode_bit()
19 Correct 73 ms 6948 KB Output is partially correct - 180980 call(s) of encode_bit()
20 Correct 116 ms 8660 KB Output is partially correct - 219820 call(s) of encode_bit()
21 Correct 129 ms 8856 KB Output is partially correct - 232820 call(s) of encode_bit()
22 Correct 117 ms 9072 KB Output is partially correct - 347200 call(s) of encode_bit()
23 Correct 137 ms 10216 KB Output is partially correct - 321980 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16564 KB Output is partially correct - 364600 call(s) of encode_bit()
2 Correct 3 ms 4452 KB Output is correct - 190 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is partially correct - 78680 call(s) of encode_bit()
4 Correct 3 ms 4552 KB Output is correct - 230 call(s) of encode_bit()
5 Correct 50 ms 6888 KB Output is partially correct - 192840 call(s) of encode_bit()
6 Correct 51 ms 6844 KB Output is partially correct - 198280 call(s) of encode_bit()
7 Correct 110 ms 9064 KB Output is partially correct - 372000 call(s) of encode_bit()
8 Correct 24 ms 5156 KB Output is correct - 46130 call(s) of encode_bit()
9 Correct 20 ms 5312 KB Output is correct - 51020 call(s) of encode_bit()
10 Correct 26 ms 5344 KB Output is correct - 48940 call(s) of encode_bit()
11 Correct 44 ms 6084 KB Output is partially correct - 104700 call(s) of encode_bit()
12 Correct 18 ms 5040 KB Output is correct - 29980 call(s) of encode_bit()
13 Correct 98 ms 8224 KB Output is partially correct - 251560 call(s) of encode_bit()
14 Correct 35 ms 5328 KB Output is correct - 55440 call(s) of encode_bit()
15 Correct 33 ms 5536 KB Output is correct - 58540 call(s) of encode_bit()
16 Correct 78 ms 6740 KB Output is partially correct - 117020 call(s) of encode_bit()
17 Correct 73 ms 6532 KB Output is partially correct - 109220 call(s) of encode_bit()
18 Correct 86 ms 7576 KB Output is partially correct - 172320 call(s) of encode_bit()
19 Correct 73 ms 6948 KB Output is partially correct - 180980 call(s) of encode_bit()
20 Correct 116 ms 8660 KB Output is partially correct - 219820 call(s) of encode_bit()
21 Correct 129 ms 8856 KB Output is partially correct - 232820 call(s) of encode_bit()
22 Correct 117 ms 9072 KB Output is partially correct - 347200 call(s) of encode_bit()
23 Correct 137 ms 10216 KB Output is partially correct - 321980 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16564 KB Output is partially correct - 364600 call(s) of encode_bit()
2 Correct 3 ms 4452 KB Output is correct - 190 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is partially correct - 78680 call(s) of encode_bit()
4 Correct 3 ms 4552 KB Output is correct - 230 call(s) of encode_bit()
5 Correct 50 ms 6888 KB Output is partially correct - 192840 call(s) of encode_bit()
6 Correct 51 ms 6844 KB Output is partially correct - 198280 call(s) of encode_bit()
7 Correct 110 ms 9064 KB Output is partially correct - 372000 call(s) of encode_bit()
8 Correct 24 ms 5156 KB Output is correct - 46130 call(s) of encode_bit()
9 Correct 20 ms 5312 KB Output is correct - 51020 call(s) of encode_bit()
10 Correct 26 ms 5344 KB Output is correct - 48940 call(s) of encode_bit()
11 Correct 44 ms 6084 KB Output is partially correct - 104700 call(s) of encode_bit()
12 Correct 18 ms 5040 KB Output is correct - 29980 call(s) of encode_bit()
13 Correct 98 ms 8224 KB Output is partially correct - 251560 call(s) of encode_bit()
14 Correct 35 ms 5328 KB Output is correct - 55440 call(s) of encode_bit()
15 Correct 33 ms 5536 KB Output is correct - 58540 call(s) of encode_bit()
16 Correct 78 ms 6740 KB Output is partially correct - 117020 call(s) of encode_bit()
17 Correct 73 ms 6532 KB Output is partially correct - 109220 call(s) of encode_bit()
18 Correct 86 ms 7576 KB Output is partially correct - 172320 call(s) of encode_bit()
19 Correct 73 ms 6948 KB Output is partially correct - 180980 call(s) of encode_bit()
20 Correct 116 ms 8660 KB Output is partially correct - 219820 call(s) of encode_bit()
21 Correct 129 ms 8856 KB Output is partially correct - 232820 call(s) of encode_bit()
22 Correct 117 ms 9072 KB Output is partially correct - 347200 call(s) of encode_bit()
23 Correct 137 ms 10216 KB Output is partially correct - 321980 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16564 KB Output is partially correct - 364600 call(s) of encode_bit()
2 Correct 3 ms 4452 KB Output is correct - 190 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is partially correct - 78680 call(s) of encode_bit()
4 Correct 3 ms 4552 KB Output is correct - 230 call(s) of encode_bit()
5 Correct 50 ms 6888 KB Output is partially correct - 192840 call(s) of encode_bit()
6 Correct 51 ms 6844 KB Output is partially correct - 198280 call(s) of encode_bit()
7 Correct 110 ms 9064 KB Output is partially correct - 372000 call(s) of encode_bit()
8 Correct 24 ms 5156 KB Output is correct - 46130 call(s) of encode_bit()
9 Correct 20 ms 5312 KB Output is correct - 51020 call(s) of encode_bit()
10 Correct 26 ms 5344 KB Output is correct - 48940 call(s) of encode_bit()
11 Correct 44 ms 6084 KB Output is partially correct - 104700 call(s) of encode_bit()
12 Correct 18 ms 5040 KB Output is correct - 29980 call(s) of encode_bit()
13 Correct 98 ms 8224 KB Output is partially correct - 251560 call(s) of encode_bit()
14 Correct 35 ms 5328 KB Output is correct - 55440 call(s) of encode_bit()
15 Correct 33 ms 5536 KB Output is correct - 58540 call(s) of encode_bit()
16 Correct 78 ms 6740 KB Output is partially correct - 117020 call(s) of encode_bit()
17 Correct 73 ms 6532 KB Output is partially correct - 109220 call(s) of encode_bit()
18 Correct 86 ms 7576 KB Output is partially correct - 172320 call(s) of encode_bit()
19 Correct 73 ms 6948 KB Output is partially correct - 180980 call(s) of encode_bit()
20 Correct 116 ms 8660 KB Output is partially correct - 219820 call(s) of encode_bit()
21 Correct 129 ms 8856 KB Output is partially correct - 232820 call(s) of encode_bit()
22 Correct 117 ms 9072 KB Output is partially correct - 347200 call(s) of encode_bit()
23 Correct 137 ms 10216 KB Output is partially correct - 321980 call(s) of encode_bit()