oj.uz

Submission #476592

# Submission time Handle Problem Language Result Execution time Memory
476592 2021-09-27T18:05:25 Z AdamGS Saveit (IOI10_saveit) C++14
100 / 100
 290 ms 13440 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) {
			ll 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], zero[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, h) zero[i]=wczytaj(10);
	rep(i, P.size()-1) {
		T[i+1]=wczytaj(58);
	}
	rep(i, h) {
		rep(j, n) odl[j]=0;
		odl[0]=zero[i];
		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:37:2: note: in expansion of macro 'rep'
   37 |  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:43:3: note: in expansion of macro 'rep'
   43 |   rep(j, P.size()-1) {
      |   ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 13440 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 3 ms 4588 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 22 ms 5524 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4580 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 31 ms 5732 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 30 ms 5844 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 43 ms 6296 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 26 ms 5516 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 25 ms 5520 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 23 ms 5544 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 38 ms 5712 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 26 ms 5500 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 71 ms 6616 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 26 ms 5488 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 26 ms 5764 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 47 ms 6264 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 53 ms 6288 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 66 ms 6772 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 35 ms 6180 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 64 ms 7184 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 92 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 50 ms 6604 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 99 ms 7944 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 13440 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 3 ms 4588 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 22 ms 5524 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4580 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 31 ms 5732 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 30 ms 5844 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 43 ms 6296 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 26 ms 5516 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 25 ms 5520 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 23 ms 5544 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 38 ms 5712 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 26 ms 5500 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 71 ms 6616 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 26 ms 5488 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 26 ms 5764 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 47 ms 6264 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 53 ms 6288 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 66 ms 6772 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 35 ms 6180 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 64 ms 7184 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 92 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 50 ms 6604 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 99 ms 7944 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 13440 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 3 ms 4588 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 22 ms 5524 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4580 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 31 ms 5732 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 30 ms 5844 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 43 ms 6296 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 26 ms 5516 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 25 ms 5520 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 23 ms 5544 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 38 ms 5712 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 26 ms 5500 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 71 ms 6616 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 26 ms 5488 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 26 ms 5764 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 47 ms 6264 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 53 ms 6288 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 66 ms 6772 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 35 ms 6180 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 64 ms 7184 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 92 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 50 ms 6604 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 99 ms 7944 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 13440 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 3 ms 4588 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 22 ms 5524 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4580 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 31 ms 5732 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 30 ms 5844 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 43 ms 6296 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 26 ms 5516 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 25 ms 5520 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 23 ms 5544 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 38 ms 5712 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 26 ms 5500 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 71 ms 6616 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 26 ms 5488 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 26 ms 5764 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 47 ms 6264 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 53 ms 6288 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 66 ms 6772 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 35 ms 6180 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 64 ms 7184 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 92 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 50 ms 6604 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 99 ms 7944 KB Output is correct - 68292 call(s) of encode_bit()