oj.uz

Submission #476565

# Submission time Handle Problem Language Result Execution time Memory
476565 2021-09-27T16:00:12 Z AdamGS Saveit (IOI10_saveit) C++14
0 / 100
 283 ms 13344 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7, INF=1e9+7;
vector<ll>V[LIM], P;
ll oc[LIM], odw[LIM], odl[LIM], T[LIM];
void DFS(int x) {
	P.pb(x);
	odw[x]=1;
	sort(all(V[x]));
	for(auto i : V[x]) if(!odw[i]) {
		oc[i]=x;
		DFS(i);
	}
}
void encode(int n, int h, int m, int *a, int *b) {
	rep(i, m) {
		V[a[i]].pb(b[i]);
		V[b[i]].pb(a[i]);
	}
	DFS(0);
	rep(i, n-1) rep(j, 10) encode_bit((oc[i+1]&(1<<j))>0);
	ll akt=1;
	rep(i, h) {
		rep(j, n) odl[j]=INF;
		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, 10) encode_bit((odl[0]&(1<<j))>0);
		rep(j, P.size()-1) {
			int x=odl[P[j+1]]-odl[oc[P[j+1]]]+1;
			T[j+1]+=akt*x;
		}
		akt*=3;
	}
	rep(i, P.size()-1) {
		rep(l, 58) encode_bit((T[i+1]&(1ll<<l))>0);
	}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7;
vector<int>V[LIM], P;
ll odw[LIM], oc[LIM], odl[LIM], T[LIM];
void DFS(int x) {
	P.pb(x);
	odw[x]=1;
	sort(all(V[x]));
	for(auto i : V[x]) if(!odw[i]) DFS(i);
}
void decode(int n, int h) {
	rep(i, n-1) {
		int x=0;
		rep(j, 10) x+=decode_bit()*(1<<j);
		oc[i+1]=x;
		V[i+1].pb(x);
		V[x].pb(i+1);
	}
	DFS(0);
	rep(i, P.size()-1) {
		rep(j, 58) T[i+1]+=decode_bit()*(1ll<<j);
	}
	rep(i, h) {
		rep(j, n) odl[j]=0;
		rep(j, 10) odl[0]+=decode_bit()*(1<<j);
		rep(j, P.size()-1) {
			int x=T[j+1]%3; T[j+1]/=3;
			--x;
			odl[P[j+1]]=odl[oc[P[j+1]]]+x;
		}
		rep(j, n) hops(i, j, odl[j]);
	}
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(ll a = 0; a < (b); ++a)
      |                                   ^
encoder.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(j, P.size()-1) {
      |   ^~~
encoder.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(ll a = 0; a < (b); ++a)
      |                                   ^
encoder.cpp:51:2: note: in expansion of macro 'rep'
   51 |  rep(i, P.size()-1) {
      |  ^~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(ll a = 0; a < (b); ++a)
      |                                   ^
decoder.cpp:30:2: note: in expansion of macro 'rep'
   30 |  rep(i, P.size()-1) {
      |  ^~~
decoder.cpp:7:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(ll a = 0; a < (b); ++a)
      |                                   ^
decoder.cpp:36:3: note: in expansion of macro 'rep'
   36 |   rep(j, P.size()-1) {
      |   ^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 13344 KB wrong parameter
2 Incorrect 3 ms 4580 KB Output isn't correct
3 Incorrect 23 ms 5448 KB wrong parameter
4 Incorrect 3 ms 4588 KB wrong parameter
5 Incorrect 26 ms 5720 KB wrong parameter
6 Incorrect 24 ms 5816 KB wrong parameter
7 Incorrect 48 ms 6352 KB wrong parameter
8 Incorrect 22 ms 5468 KB wrong parameter
9 Incorrect 26 ms 5528 KB wrong parameter
10 Incorrect 25 ms 5476 KB wrong parameter
11 Incorrect 27 ms 5772 KB wrong parameter
12 Incorrect 20 ms 5448 KB wrong parameter
13 Incorrect 61 ms 6636 KB Output isn't correct
14 Incorrect 23 ms 5532 KB wrong parameter
15 Incorrect 24 ms 5596 KB wrong parameter
16 Incorrect 47 ms 6312 KB wrong parameter
17 Incorrect 50 ms 6284 KB wrong parameter
18 Incorrect 74 ms 6716 KB wrong parameter
19 Incorrect 43 ms 6136 KB wrong parameter
20 Incorrect 80 ms 7192 KB wrong parameter
21 Incorrect 86 ms 7472 KB wrong parameter
22 Incorrect 63 ms 6536 KB wrong parameter
23 Incorrect 100 ms 7756 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 13344 KB wrong parameter
2 Incorrect 3 ms 4580 KB Output isn't correct
3 Incorrect 23 ms 5448 KB wrong parameter
4 Incorrect 3 ms 4588 KB wrong parameter
5 Incorrect 26 ms 5720 KB wrong parameter
6 Incorrect 24 ms 5816 KB wrong parameter
7 Incorrect 48 ms 6352 KB wrong parameter
8 Incorrect 22 ms 5468 KB wrong parameter
9 Incorrect 26 ms 5528 KB wrong parameter
10 Incorrect 25 ms 5476 KB wrong parameter
11 Incorrect 27 ms 5772 KB wrong parameter
12 Incorrect 20 ms 5448 KB wrong parameter
13 Incorrect 61 ms 6636 KB Output isn't correct
14 Incorrect 23 ms 5532 KB wrong parameter
15 Incorrect 24 ms 5596 KB wrong parameter
16 Incorrect 47 ms 6312 KB wrong parameter
17 Incorrect 50 ms 6284 KB wrong parameter
18 Incorrect 74 ms 6716 KB wrong parameter
19 Incorrect 43 ms 6136 KB wrong parameter
20 Incorrect 80 ms 7192 KB wrong parameter
21 Incorrect 86 ms 7472 KB wrong parameter
22 Incorrect 63 ms 6536 KB wrong parameter
23 Incorrect 100 ms 7756 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 13344 KB wrong parameter
2 Incorrect 3 ms 4580 KB Output isn't correct
3 Incorrect 23 ms 5448 KB wrong parameter
4 Incorrect 3 ms 4588 KB wrong parameter
5 Incorrect 26 ms 5720 KB wrong parameter
6 Incorrect 24 ms 5816 KB wrong parameter
7 Incorrect 48 ms 6352 KB wrong parameter
8 Incorrect 22 ms 5468 KB wrong parameter
9 Incorrect 26 ms 5528 KB wrong parameter
10 Incorrect 25 ms 5476 KB wrong parameter
11 Incorrect 27 ms 5772 KB wrong parameter
12 Incorrect 20 ms 5448 KB wrong parameter
13 Incorrect 61 ms 6636 KB Output isn't correct
14 Incorrect 23 ms 5532 KB wrong parameter
15 Incorrect 24 ms 5596 KB wrong parameter
16 Incorrect 47 ms 6312 KB wrong parameter
17 Incorrect 50 ms 6284 KB wrong parameter
18 Incorrect 74 ms 6716 KB wrong parameter
19 Incorrect 43 ms 6136 KB wrong parameter
20 Incorrect 80 ms 7192 KB wrong parameter
21 Incorrect 86 ms 7472 KB wrong parameter
22 Incorrect 63 ms 6536 KB wrong parameter
23 Incorrect 100 ms 7756 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 13344 KB wrong parameter
2 Incorrect 3 ms 4580 KB Output isn't correct
3 Incorrect 23 ms 5448 KB wrong parameter
4 Incorrect 3 ms 4588 KB wrong parameter
5 Incorrect 26 ms 5720 KB wrong parameter
6 Incorrect 24 ms 5816 KB wrong parameter
7 Incorrect 48 ms 6352 KB wrong parameter
8 Incorrect 22 ms 5468 KB wrong parameter
9 Incorrect 26 ms 5528 KB wrong parameter
10 Incorrect 25 ms 5476 KB wrong parameter
11 Incorrect 27 ms 5772 KB wrong parameter
12 Incorrect 20 ms 5448 KB wrong parameter
13 Incorrect 61 ms 6636 KB Output isn't correct
14 Incorrect 23 ms 5532 KB wrong parameter
15 Incorrect 24 ms 5596 KB wrong parameter
16 Incorrect 47 ms 6312 KB wrong parameter
17 Incorrect 50 ms 6284 KB wrong parameter
18 Incorrect 74 ms 6716 KB wrong parameter
19 Incorrect 43 ms 6136 KB wrong parameter
20 Incorrect 80 ms 7192 KB wrong parameter
21 Incorrect 86 ms 7472 KB wrong parameter
22 Incorrect 63 ms 6536 KB wrong parameter
23 Incorrect 100 ms 7756 KB wrong parameter