oj.uz

Submission #1061500

# Submission time Handle Problem Language Result Execution time Memory
1061500 2024-08-16T09:59:06 Z thieunguyenhuy Saveit (IOI10_saveit) C++17
0 / 100
 149 ms 21156 KB 
#ifndef hwe
	#include "grader.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1000, H = 36;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

int dist[H][N], par[N];
vector<int> adj[N];

#ifdef hwe
void encode_bit(int bit) {
	cerr << bit;
}
#endif

void bfs(int root) {
	memset(dist[root], 0x3f, sizeof dist[root]);
	queue<int> q; q.emplace(root); dist[root][root] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v : adj[u]) if (minimize(dist[root][v], dist[root][u] + 1)) {
			q.emplace(v);
			if (root == 0) par[v] = u;
		}
	}
}

void encode(int n, int h, int m, int *a, int *b) {
	for (int i = 0; i < n; ++i) {
		adj[i].clear(), par[i] = -1;
	}
	int LOG = lg(n) + 1;

	for (int i = 0; i < m; ++i) {
		int u = a[i], v = b[i];
		adj[u].emplace_back(v), adj[v].emplace_back(u);
	}

	for (int i = 0; i < h; ++i) bfs(i);

	// send the spanning tree by the parent of each node in the tree
	for (int i = 1; i < n; ++i)  for (int j = LOG - 1; j >= 0; --j) {
		encode_bit(BIT(par[i], j));
	}
	// cerr << "Done tree\n";

	for (int hub = 0; hub < h; ++hub) {
		for (int i = 1; i < n; i += 3) {
			int num = 0, cnt = 0;
			for (int j = i; j < min(i + 3, n); ++j) {
				int send = dist[hub][j] - dist[hub][par[j]] + 1;
				num = num * 3 + send, ++cnt;
			}
			while (cnt < 3) num = num * 3, ++cnt;
			for (int j = 4; j >= 0; --j) encode_bit(BIT(num, j));
		}
	}
}

#ifdef hwe
signed main() {
	int n = 3, h = 1, m = 2;
	int a[m], b[m];
	a[0] = 0, b[0] = 1;
	a[1] = 0, b[1] = 2;

	encode(n, h, m, a, b);

    cerr << '\n'; return 0;
}
#endif

#ifndef hwe
	#include "grader.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1000, H = 36;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

int dep[N], par[N], dif[N], dist[N];
vector<int> adj[N];

void decode(int n, int h) {
	for (int i = 0; i < n; ++i) {
		adj[i].clear(), dep[i] = -1;
	}
	int LOG = lg(n) + 1;

	for (int i = 1; i < n; ++i) {
		par[i] = 0;
		for (int j = LOG - 1; j >= 0; --j) par[i] = par[i] * 2 + decode_bit();
		adj[par[i]].emplace_back(i);
	}

	queue<int> q; q.emplace(0); dep[0] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v : adj[u]) if (dep[v] == -1) {
			dep[v] = dep[u] + 1;
			q.emplace(v);
		}
	}

	vector<int> order(n - 1); iota(order.begin(), order.end(), 1);
	sort (order.begin(), order.end(), [&](int x, int y) {
		return dep[x] < dep[y];
	});

	for (int hub = 0; hub < h; ++hub) {
		memset(dist, -1, sizeof dist);
		dist[hub] = 0;
		
		for (int i = 1; i < n; i += 3) {
			int num = 0;
			for (int j = 4; j >= 0; --j) num = num << 1 | decode_bit();
			vector<int> sends;
			while (num > 0) sends.emplace_back(num % 3), num /= 3;
			reverse(sends.begin(), sends.end());
			for (int j = i; j < min(i + 3, n); ++j) dif[i] = sends[j - i] - 1;
		}

		int u = hub;
		while (u != 0) {
			dist[par[u]] = dist[u] - dif[u];
			u = par[u];
		}

		assert(dist[0] != -1);

		for (auto u : order) {
			if (dist[u] != -1) continue;
			dist[u] = dist[par[u]] + dif[u];
		}

		for (int i = 0; i < n; ++i) hops(hub, i, dist[i]);
	}
}

#ifdef hwe
signed main() {


    cerr << '\n'; return 0;
}
#endif

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 21156 KB Execution killed with signal 11
2 Incorrect 1 ms 11264 KB Output isn't correct
3 Runtime error 14 ms 16124 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 25 ms 16124 KB Execution killed with signal 11
7 Incorrect 22 ms 11948 KB wrong parameter
8 Runtime error 18 ms 16172 KB Execution killed with signal 11
9 Incorrect 15 ms 11520 KB wrong parameter
10 Runtime error 20 ms 16072 KB Execution killed with signal 11
11 Runtime error 18 ms 16124 KB Execution killed with signal 11
12 Runtime error 19 ms 15992 KB Execution killed with signal 11
13 Incorrect 42 ms 11952 KB wrong parameter
14 Runtime error 22 ms 16124 KB Execution killed with signal 11
15 Runtime error 23 ms 15996 KB Execution killed with signal 11
16 Runtime error 27 ms 16388 KB Execution killed with signal 11
17 Runtime error 26 ms 16300 KB Execution killed with signal 11
18 Runtime error 33 ms 16620 KB Execution killed with signal 11
19 Incorrect 28 ms 11692 KB wrong parameter
20 Runtime error 41 ms 18860 KB Execution killed with signal 11
21 Incorrect 39 ms 14312 KB wrong parameter
22 Incorrect 30 ms 11948 KB wrong parameter
23 Runtime error 51 ms 19224 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 21156 KB Execution killed with signal 11
2 Incorrect 1 ms 11264 KB Output isn't correct
3 Runtime error 14 ms 16124 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 25 ms 16124 KB Execution killed with signal 11
7 Incorrect 22 ms 11948 KB wrong parameter
8 Runtime error 18 ms 16172 KB Execution killed with signal 11
9 Incorrect 15 ms 11520 KB wrong parameter
10 Runtime error 20 ms 16072 KB Execution killed with signal 11
11 Runtime error 18 ms 16124 KB Execution killed with signal 11
12 Runtime error 19 ms 15992 KB Execution killed with signal 11
13 Incorrect 42 ms 11952 KB wrong parameter
14 Runtime error 22 ms 16124 KB Execution killed with signal 11
15 Runtime error 23 ms 15996 KB Execution killed with signal 11
16 Runtime error 27 ms 16388 KB Execution killed with signal 11
17 Runtime error 26 ms 16300 KB Execution killed with signal 11
18 Runtime error 33 ms 16620 KB Execution killed with signal 11
19 Incorrect 28 ms 11692 KB wrong parameter
20 Runtime error 41 ms 18860 KB Execution killed with signal 11
21 Incorrect 39 ms 14312 KB wrong parameter
22 Incorrect 30 ms 11948 KB wrong parameter
23 Runtime error 51 ms 19224 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 21156 KB Execution killed with signal 11
2 Incorrect 1 ms 11264 KB Output isn't correct
3 Runtime error 14 ms 16124 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 25 ms 16124 KB Execution killed with signal 11
7 Incorrect 22 ms 11948 KB wrong parameter
8 Runtime error 18 ms 16172 KB Execution killed with signal 11
9 Incorrect 15 ms 11520 KB wrong parameter
10 Runtime error 20 ms 16072 KB Execution killed with signal 11
11 Runtime error 18 ms 16124 KB Execution killed with signal 11
12 Runtime error 19 ms 15992 KB Execution killed with signal 11
13 Incorrect 42 ms 11952 KB wrong parameter
14 Runtime error 22 ms 16124 KB Execution killed with signal 11
15 Runtime error 23 ms 15996 KB Execution killed with signal 11
16 Runtime error 27 ms 16388 KB Execution killed with signal 11
17 Runtime error 26 ms 16300 KB Execution killed with signal 11
18 Runtime error 33 ms 16620 KB Execution killed with signal 11
19 Incorrect 28 ms 11692 KB wrong parameter
20 Runtime error 41 ms 18860 KB Execution killed with signal 11
21 Incorrect 39 ms 14312 KB wrong parameter
22 Incorrect 30 ms 11948 KB wrong parameter
23 Runtime error 51 ms 19224 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 21156 KB Execution killed with signal 11
2 Incorrect 1 ms 11264 KB Output isn't correct
3 Runtime error 14 ms 16124 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 25 ms 16124 KB Execution killed with signal 11
7 Incorrect 22 ms 11948 KB wrong parameter
8 Runtime error 18 ms 16172 KB Execution killed with signal 11
9 Incorrect 15 ms 11520 KB wrong parameter
10 Runtime error 20 ms 16072 KB Execution killed with signal 11
11 Runtime error 18 ms 16124 KB Execution killed with signal 11
12 Runtime error 19 ms 15992 KB Execution killed with signal 11
13 Incorrect 42 ms 11952 KB wrong parameter
14 Runtime error 22 ms 16124 KB Execution killed with signal 11
15 Runtime error 23 ms 15996 KB Execution killed with signal 11
16 Runtime error 27 ms 16388 KB Execution killed with signal 11
17 Runtime error 26 ms 16300 KB Execution killed with signal 11
18 Runtime error 33 ms 16620 KB Execution killed with signal 11
19 Incorrect 28 ms 11692 KB wrong parameter
20 Runtime error 41 ms 18860 KB Execution killed with signal 11
21 Incorrect 39 ms 14312 KB wrong parameter
22 Incorrect 30 ms 11948 KB wrong parameter
23 Runtime error 51 ms 19224 KB Execution killed with signal 11