oj.uz

Submission #476571

# Submission time Handle Problem Language Result Execution time Memory
476571 2021-09-27T16:15:37 Z AdamGS Saveit (IOI10_saveit) C++14
0 / 100
 206 ms 13312 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);
}
ll wczytaj(ll x) {
	ll ans=0;
	rep(i, x) {
		if(decode_bit()) ans+=1ll<<i;
	}
	return ans;
}
void decode(int n, int h) {
	rep(i, n-1) {
		int x=wczytaj(10);
		oc[i+1]=x;
		V[i+1].pb(x);
		V[x].pb(i+1);
	}
	DFS(0);
	rep(i, P.size()-1) {
		T[i+1]=wczytaj(58);
	}
	rep(i, h) {
		rep(j, n) odl[j]=0;
		odl[0]=wczytaj(10);
		rep(j, P.size()-1) {
			ll 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:36:2: note: in expansion of macro 'rep'
   36 |  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:42:3: note: in expansion of macro 'rep'
   42 |   rep(j, P.size()-1) {
      |   ^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 13312 KB wrong parameter
2 Incorrect 2 ms 4588 KB Output isn't correct
3 Incorrect 20 ms 5476 KB wrong parameter
4 Incorrect 2 ms 4592 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 24 ms 5852 KB wrong parameter
7 Incorrect 42 ms 6400 KB wrong parameter
8 Incorrect 20 ms 5584 KB wrong parameter
9 Incorrect 30 ms 5412 KB wrong parameter
10 Incorrect 27 ms 5396 KB wrong parameter
11 Incorrect 27 ms 5668 KB wrong parameter
12 Incorrect 20 ms 5612 KB wrong parameter
13 Incorrect 61 ms 6536 KB Output isn't correct
14 Incorrect 22 ms 5548 KB wrong parameter
15 Incorrect 28 ms 5568 KB wrong parameter
16 Incorrect 65 ms 6172 KB wrong parameter
17 Incorrect 44 ms 6288 KB wrong parameter
18 Incorrect 62 ms 6680 KB wrong parameter
19 Incorrect 37 ms 6092 KB wrong parameter
20 Incorrect 75 ms 7188 KB wrong parameter
21 Incorrect 82 ms 7336 KB wrong parameter
22 Incorrect 61 ms 6632 KB wrong parameter
23 Incorrect 97 ms 7864 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 13312 KB wrong parameter
2 Incorrect 2 ms 4588 KB Output isn't correct
3 Incorrect 20 ms 5476 KB wrong parameter
4 Incorrect 2 ms 4592 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 24 ms 5852 KB wrong parameter
7 Incorrect 42 ms 6400 KB wrong parameter
8 Incorrect 20 ms 5584 KB wrong parameter
9 Incorrect 30 ms 5412 KB wrong parameter
10 Incorrect 27 ms 5396 KB wrong parameter
11 Incorrect 27 ms 5668 KB wrong parameter
12 Incorrect 20 ms 5612 KB wrong parameter
13 Incorrect 61 ms 6536 KB Output isn't correct
14 Incorrect 22 ms 5548 KB wrong parameter
15 Incorrect 28 ms 5568 KB wrong parameter
16 Incorrect 65 ms 6172 KB wrong parameter
17 Incorrect 44 ms 6288 KB wrong parameter
18 Incorrect 62 ms 6680 KB wrong parameter
19 Incorrect 37 ms 6092 KB wrong parameter
20 Incorrect 75 ms 7188 KB wrong parameter
21 Incorrect 82 ms 7336 KB wrong parameter
22 Incorrect 61 ms 6632 KB wrong parameter
23 Incorrect 97 ms 7864 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 13312 KB wrong parameter
2 Incorrect 2 ms 4588 KB Output isn't correct
3 Incorrect 20 ms 5476 KB wrong parameter
4 Incorrect 2 ms 4592 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 24 ms 5852 KB wrong parameter
7 Incorrect 42 ms 6400 KB wrong parameter
8 Incorrect 20 ms 5584 KB wrong parameter
9 Incorrect 30 ms 5412 KB wrong parameter
10 Incorrect 27 ms 5396 KB wrong parameter
11 Incorrect 27 ms 5668 KB wrong parameter
12 Incorrect 20 ms 5612 KB wrong parameter
13 Incorrect 61 ms 6536 KB Output isn't correct
14 Incorrect 22 ms 5548 KB wrong parameter
15 Incorrect 28 ms 5568 KB wrong parameter
16 Incorrect 65 ms 6172 KB wrong parameter
17 Incorrect 44 ms 6288 KB wrong parameter
18 Incorrect 62 ms 6680 KB wrong parameter
19 Incorrect 37 ms 6092 KB wrong parameter
20 Incorrect 75 ms 7188 KB wrong parameter
21 Incorrect 82 ms 7336 KB wrong parameter
22 Incorrect 61 ms 6632 KB wrong parameter
23 Incorrect 97 ms 7864 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 13312 KB wrong parameter
2 Incorrect 2 ms 4588 KB Output isn't correct
3 Incorrect 20 ms 5476 KB wrong parameter
4 Incorrect 2 ms 4592 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 24 ms 5852 KB wrong parameter
7 Incorrect 42 ms 6400 KB wrong parameter
8 Incorrect 20 ms 5584 KB wrong parameter
9 Incorrect 30 ms 5412 KB wrong parameter
10 Incorrect 27 ms 5396 KB wrong parameter
11 Incorrect 27 ms 5668 KB wrong parameter
12 Incorrect 20 ms 5612 KB wrong parameter
13 Incorrect 61 ms 6536 KB Output isn't correct
14 Incorrect 22 ms 5548 KB wrong parameter
15 Incorrect 28 ms 5568 KB wrong parameter
16 Incorrect 65 ms 6172 KB wrong parameter
17 Incorrect 44 ms 6288 KB wrong parameter
18 Incorrect 62 ms 6680 KB wrong parameter
19 Incorrect 37 ms 6092 KB wrong parameter
20 Incorrect 75 ms 7188 KB wrong parameter
21 Incorrect 82 ms 7336 KB wrong parameter
22 Incorrect 61 ms 6632 KB wrong parameter
23 Incorrect 97 ms 7864 KB wrong parameter