oj.uz

Submission #366591

# Submission time Handle Problem Language Result Execution time Memory
366591 2021-02-14T17:31:42 Z kostia244 Saveit (IOI10_saveit) C++17
100 / 100
 823 ms 20716 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
	uint a[SZ];
	big_int() {
		memset(a, 0, sizeof a);
	}
	void triple() {
		for(int i = 0; i < SZ; i++) a[i] *= 3;
		for(int i = 0; i+1 < SZ; i++) {
			a[i+1] += a[i]>>30;
			a[i] &= ful;
		}
	}
	void add(uint x) {
		int co = x;
		for(int i = 0; co;) {
			a[i] += co;
			co = a[i]>>30;
			a[i] &= ful;
		}
	}
	friend big_int operator+(big_int x, const big_int &y) {
		uint co = 0;
		for(int i = 0; i < SZ; i++) {
			x.a[i] += y.a[i]+co;
			co = x.a[i]>>30;
			x.a[i] &= ful;
		}
		return x;
	}
	friend bool operator<=(const big_int &a, const big_int &b) {
		int pos = SZ-1;
		while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
		return pos == -1 || a.a[pos] <= b.a[pos];
	}
	void send() {
		for(int i = 0; i < N; i++) {
			int val = a[i/30];
			val >>= i%30;
			encode_bit(val&1);
		}
	}
	void get() {
		for(int i = 0; i < N; i++) {
			int val = decode_bit();
			val <<= i%30;
			a[i/30] |= val;
		}
	}
	void print() {
		for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
	}
};
int n, par[N];
vector<int> g[N];
template<int build_tree>
void bfs(int v) {
	vector<int> dist(n+1, -1);
	queue<int> q;
	auto enq = [&](int v, int d, int P) {
		if(dist[v] != -1) return;
		dist[v] = d;
		if(build_tree) par[v] = P;
		q.push(v);
	};
	enq(v, 0, -1);
	while(!q.empty()) {
		int v = q.front();q.pop();
		for(auto i : g[v]) enq(i, dist[v]+1, v);
	}
	//for(int i = 0; i < n; i++) cout << dist[i] << " "; cout << endl;
	if(build_tree) {
		for(int i = 1; i < n; i++)
			for(int j = 0; j < 10; j++)
				encode_bit((par[i]>>j)&1);
	} else {
		for(int i = 0; i < 10; i++) encode_bit((dist[0]>>i)&1);
		big_int res;
		for(int i = 1; i < n; i++) {
			res.triple();
			res.add(1 + dist[i] - dist[par[i]]);
			//cout << v << " | " << i << " | " << 1 + dist[i] - dist[par[i]] << " res " << dist[i] << endl;
		}
		//cout << v << " res " << res.a[0] << endl;
		res.send();
	}
}
};
void encode(int V, int H, int E, int *v1, int *v2){
	n = V;
	for(int i = 0; i < E; i++) g[v1[i]].push_back(v2[i]);
	for(int i = 0; i < E; i++) g[v2[i]].push_back(v1[i]);
	bfs<1>(0);
	for(int i = 1; i < H; i++) bfs<0>(i);
	return;
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
	uint a[SZ];
	big_int() {
		memset(a, 0, sizeof a);
	}
	void triple() {
		for(int i = 0; i < SZ; i++) a[i] *= 3;
		for(int i = 0; i+1 < SZ; i++) {
			a[i+1] += a[i]>>30;
			a[i] &= ful;
		}
	}
	void add(uint x) {
		int co = x;
		for(int i = 0; co;) {
			a[i] += co;
			co = a[i]>>30;
			a[i] &= ful;
		}
	}
	friend big_int operator+(big_int x, const big_int &y) {
		uint co = 0;
		for(int i = 0; i < SZ; i++) {
			x.a[i] += y.a[i]+co;
			co = x.a[i]>>30;
			x.a[i] &= ful;
		}
		return x;
	}
	friend bool operator<=(const big_int &a, const big_int &b) {
		int pos = SZ-1;
		while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
		return pos == -1 || a.a[pos] <= b.a[pos];
	}
	void send() {
		for(int i = 0; i < N; i++) {
			int val = a[i/30];
			val >>= i%30;
			encode_bit(val&1);
		}
	}
	void get() {
		for(int i = 0; i < N; i++) {
			int val = decode_bit();
			val <<= i%30;
			a[i/30] |= val;
		}
	}
	void print() {
		for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
	}
};
int n, h, d21[N], par[N];
vector<int> g[N], ord;
void dfs(int v) {
	ord.push_back(v);
	for(int i : g[v]) dfs(i);
}
big_int pws[N];
}
void decode(int nv, int nh) {
	n = nv;
	h = nh;
	d21[0] = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < 10; j++) {
			par[i] |= decode_bit()<<j;
		}
		g[par[i]].push_back(i);
	}
	dfs(0);
	//cout << "pT2\n";
	for(auto i : ord) if(i) d21[i] = d21[par[i]] + 1;
	for(int i = 0; i < n; i++) hops(0, i, d21[i]);
	pws[0].add(1);
	for(int i = 1; i < n; i++) pws[i] = pws[i-1], pws[i].triple();
	for(int hl = 1; hl < h; hl++) {
		memset(d21, 0, sizeof d21);
		for(int j = 0; j < 10; j++) d21[0] |= decode_bit()<<j;
		big_int dif;
		//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
		dif.get();
		//cout << hl << " == " << dif.a[0] << endl;
		//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
		big_int cur;
		for(int i = 1; i < n; i++) {
			int CCC = 0;
			big_int &cp = pws[n-i-1], nxt;
			//cout << cur.a[0] << " " << cp.a[0] << " " << dif.a[0] << endl;
			while(nxt = cur+cp, nxt <= dif) {
				cur = nxt;
				//cout << "inc\n";
				d21[i]++;
			}
			//cout << cur.a[0] << endl;
			//cout << hl << " : " << i << " : " << d21[i] << endl;
		}
		for(auto i : ord) if(i) {
			d21[i] -= 1;
			d21[i] += d21[par[i]];
			//cout << hl << " " << i << " res " << d21[i] << endl;
		}
		for(int i = 0; i < n; i++) hops(hl, i, d21[i]);
	}
}

Compilation message

encoder.cpp: In member function 'void {anonymous}::big_int::print()':
encoder.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |   ^~~
encoder.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |                                                     ^~~~

decoder.cpp: In member function 'void {anonymous}::big_int::print()':
decoder.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |   ^~~
decoder.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |                                                     ^~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:95:8: warning: unused variable 'CCC' [-Wunused-variable]
   95 |    int CCC = 0;
      |        ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 20716 KB Output is correct - 65815 call(s) of encode_bit()
2 Correct 9 ms 15392 KB Output is correct - 3230 call(s) of encode_bit()
3 Correct 514 ms 16096 KB Output is correct - 64815 call(s) of encode_bit()
4 Correct 9 ms 15200 KB Output is correct - 6420 call(s) of encode_bit()
5 Correct 508 ms 16224 KB Output is correct - 64815 call(s) of encode_bit()
6 Correct 542 ms 16312 KB Output is correct - 65815 call(s) of encode_bit()
7 Correct 562 ms 16608 KB Output is correct - 65815 call(s) of encode_bit()
8 Correct 579 ms 16116 KB Output is correct - 65425 call(s) of encode_bit()
9 Correct 694 ms 16308 KB Output is correct - 65815 call(s) of encode_bit()
10 Correct 678 ms 16384 KB Output is correct - 65815 call(s) of encode_bit()
11 Correct 630 ms 16592 KB Output is correct - 65815 call(s) of encode_bit()
12 Correct 598 ms 16304 KB Output is correct - 65815 call(s) of encode_bit()
13 Correct 603 ms 17016 KB Output is correct - 65815 call(s) of encode_bit()
14 Correct 589 ms 16276 KB Output is correct - 65815 call(s) of encode_bit()
15 Correct 540 ms 16372 KB Output is correct - 65815 call(s) of encode_bit()
16 Correct 596 ms 16736 KB Output is correct - 65815 call(s) of encode_bit()
17 Correct 594 ms 16632 KB Output is correct - 65815 call(s) of encode_bit()
18 Correct 631 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
19 Correct 595 ms 16560 KB Output is correct - 65815 call(s) of encode_bit()
20 Correct 599 ms 17552 KB Output is correct - 65815 call(s) of encode_bit()
21 Correct 659 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
22 Correct 599 ms 17068 KB Output is correct - 65815 call(s) of encode_bit()
23 Correct 665 ms 17704 KB Output is correct - 65815 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 20716 KB Output is correct - 65815 call(s) of encode_bit()
2 Correct 9 ms 15392 KB Output is correct - 3230 call(s) of encode_bit()
3 Correct 514 ms 16096 KB Output is correct - 64815 call(s) of encode_bit()
4 Correct 9 ms 15200 KB Output is correct - 6420 call(s) of encode_bit()
5 Correct 508 ms 16224 KB Output is correct - 64815 call(s) of encode_bit()
6 Correct 542 ms 16312 KB Output is correct - 65815 call(s) of encode_bit()
7 Correct 562 ms 16608 KB Output is correct - 65815 call(s) of encode_bit()
8 Correct 579 ms 16116 KB Output is correct - 65425 call(s) of encode_bit()
9 Correct 694 ms 16308 KB Output is correct - 65815 call(s) of encode_bit()
10 Correct 678 ms 16384 KB Output is correct - 65815 call(s) of encode_bit()
11 Correct 630 ms 16592 KB Output is correct - 65815 call(s) of encode_bit()
12 Correct 598 ms 16304 KB Output is correct - 65815 call(s) of encode_bit()
13 Correct 603 ms 17016 KB Output is correct - 65815 call(s) of encode_bit()
14 Correct 589 ms 16276 KB Output is correct - 65815 call(s) of encode_bit()
15 Correct 540 ms 16372 KB Output is correct - 65815 call(s) of encode_bit()
16 Correct 596 ms 16736 KB Output is correct - 65815 call(s) of encode_bit()
17 Correct 594 ms 16632 KB Output is correct - 65815 call(s) of encode_bit()
18 Correct 631 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
19 Correct 595 ms 16560 KB Output is correct - 65815 call(s) of encode_bit()
20 Correct 599 ms 17552 KB Output is correct - 65815 call(s) of encode_bit()
21 Correct 659 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
22 Correct 599 ms 17068 KB Output is correct - 65815 call(s) of encode_bit()
23 Correct 665 ms 17704 KB Output is correct - 65815 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 20716 KB Output is correct - 65815 call(s) of encode_bit()
2 Correct 9 ms 15392 KB Output is correct - 3230 call(s) of encode_bit()
3 Correct 514 ms 16096 KB Output is correct - 64815 call(s) of encode_bit()
4 Correct 9 ms 15200 KB Output is correct - 6420 call(s) of encode_bit()
5 Correct 508 ms 16224 KB Output is correct - 64815 call(s) of encode_bit()
6 Correct 542 ms 16312 KB Output is correct - 65815 call(s) of encode_bit()
7 Correct 562 ms 16608 KB Output is correct - 65815 call(s) of encode_bit()
8 Correct 579 ms 16116 KB Output is correct - 65425 call(s) of encode_bit()
9 Correct 694 ms 16308 KB Output is correct - 65815 call(s) of encode_bit()
10 Correct 678 ms 16384 KB Output is correct - 65815 call(s) of encode_bit()
11 Correct 630 ms 16592 KB Output is correct - 65815 call(s) of encode_bit()
12 Correct 598 ms 16304 KB Output is correct - 65815 call(s) of encode_bit()
13 Correct 603 ms 17016 KB Output is correct - 65815 call(s) of encode_bit()
14 Correct 589 ms 16276 KB Output is correct - 65815 call(s) of encode_bit()
15 Correct 540 ms 16372 KB Output is correct - 65815 call(s) of encode_bit()
16 Correct 596 ms 16736 KB Output is correct - 65815 call(s) of encode_bit()
17 Correct 594 ms 16632 KB Output is correct - 65815 call(s) of encode_bit()
18 Correct 631 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
19 Correct 595 ms 16560 KB Output is correct - 65815 call(s) of encode_bit()
20 Correct 599 ms 17552 KB Output is correct - 65815 call(s) of encode_bit()
21 Correct 659 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
22 Correct 599 ms 17068 KB Output is correct - 65815 call(s) of encode_bit()
23 Correct 665 ms 17704 KB Output is correct - 65815 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 20716 KB Output is correct - 65815 call(s) of encode_bit()
2 Correct 9 ms 15392 KB Output is correct - 3230 call(s) of encode_bit()
3 Correct 514 ms 16096 KB Output is correct - 64815 call(s) of encode_bit()
4 Correct 9 ms 15200 KB Output is correct - 6420 call(s) of encode_bit()
5 Correct 508 ms 16224 KB Output is correct - 64815 call(s) of encode_bit()
6 Correct 542 ms 16312 KB Output is correct - 65815 call(s) of encode_bit()
7 Correct 562 ms 16608 KB Output is correct - 65815 call(s) of encode_bit()
8 Correct 579 ms 16116 KB Output is correct - 65425 call(s) of encode_bit()
9 Correct 694 ms 16308 KB Output is correct - 65815 call(s) of encode_bit()
10 Correct 678 ms 16384 KB Output is correct - 65815 call(s) of encode_bit()
11 Correct 630 ms 16592 KB Output is correct - 65815 call(s) of encode_bit()
12 Correct 598 ms 16304 KB Output is correct - 65815 call(s) of encode_bit()
13 Correct 603 ms 17016 KB Output is correct - 65815 call(s) of encode_bit()
14 Correct 589 ms 16276 KB Output is correct - 65815 call(s) of encode_bit()
15 Correct 540 ms 16372 KB Output is correct - 65815 call(s) of encode_bit()
16 Correct 596 ms 16736 KB Output is correct - 65815 call(s) of encode_bit()
17 Correct 594 ms 16632 KB Output is correct - 65815 call(s) of encode_bit()
18 Correct 631 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
19 Correct 595 ms 16560 KB Output is correct - 65815 call(s) of encode_bit()
20 Correct 599 ms 17552 KB Output is correct - 65815 call(s) of encode_bit()
21 Correct 659 ms 17312 KB Output is correct - 65815 call(s) of encode_bit()
22 Correct 599 ms 17068 KB Output is correct - 65815 call(s) of encode_bit()
23 Correct 665 ms 17704 KB Output is correct - 65815 call(s) of encode_bit()