oj.uz

Submission #1061499

# Submission time Handle Problem Language Result Execution time Memory
1061499 2024-08-16T09:58:30 Z thieunguyenhuy Saveit (IOI10_saveit) C++17
0 / 100
 10000 ms 21176 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;
			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 148 ms 21176 KB Execution killed with signal 11
2 Execution timed out 10074 ms 6488 KB Time limit exceeded
3 Execution timed out 10037 ms 6744 KB Time limit exceeded
4 Execution timed out 10010 ms 6488 KB Time limit exceeded
5 Execution timed out 10045 ms 6744 KB Time limit exceeded
6 Runtime error 17 ms 16364 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 18 ms 16132 KB Execution killed with signal 11
12 Runtime error 17 ms 16092 KB Execution killed with signal 11
13 Incorrect 25 ms 12048 KB wrong parameter
14 Runtime error 18 ms 15980 KB Execution killed with signal 11
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 36 ms 16292 KB Execution killed with signal 11
17 Runtime error 30 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16620 KB Execution killed with signal 11
19 Incorrect 17 ms 11780 KB wrong parameter
20 Runtime error 41 ms 18896 KB Execution killed with signal 11
21 Incorrect 41 ms 14308 KB wrong parameter
22 Incorrect 26 ms 12012 KB wrong parameter
23 Runtime error 49 ms 19172 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 21176 KB Execution killed with signal 11
2 Execution timed out 10074 ms 6488 KB Time limit exceeded
3 Execution timed out 10037 ms 6744 KB Time limit exceeded
4 Execution timed out 10010 ms 6488 KB Time limit exceeded
5 Execution timed out 10045 ms 6744 KB Time limit exceeded
6 Runtime error 17 ms 16364 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 18 ms 16132 KB Execution killed with signal 11
12 Runtime error 17 ms 16092 KB Execution killed with signal 11
13 Incorrect 25 ms 12048 KB wrong parameter
14 Runtime error 18 ms 15980 KB Execution killed with signal 11
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 36 ms 16292 KB Execution killed with signal 11
17 Runtime error 30 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16620 KB Execution killed with signal 11
19 Incorrect 17 ms 11780 KB wrong parameter
20 Runtime error 41 ms 18896 KB Execution killed with signal 11
21 Incorrect 41 ms 14308 KB wrong parameter
22 Incorrect 26 ms 12012 KB wrong parameter
23 Runtime error 49 ms 19172 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 21176 KB Execution killed with signal 11
2 Execution timed out 10074 ms 6488 KB Time limit exceeded
3 Execution timed out 10037 ms 6744 KB Time limit exceeded
4 Execution timed out 10010 ms 6488 KB Time limit exceeded
5 Execution timed out 10045 ms 6744 KB Time limit exceeded
6 Runtime error 17 ms 16364 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 18 ms 16132 KB Execution killed with signal 11
12 Runtime error 17 ms 16092 KB Execution killed with signal 11
13 Incorrect 25 ms 12048 KB wrong parameter
14 Runtime error 18 ms 15980 KB Execution killed with signal 11
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 36 ms 16292 KB Execution killed with signal 11
17 Runtime error 30 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16620 KB Execution killed with signal 11
19 Incorrect 17 ms 11780 KB wrong parameter
20 Runtime error 41 ms 18896 KB Execution killed with signal 11
21 Incorrect 41 ms 14308 KB wrong parameter
22 Incorrect 26 ms 12012 KB wrong parameter
23 Runtime error 49 ms 19172 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 21176 KB Execution killed with signal 11
2 Execution timed out 10074 ms 6488 KB Time limit exceeded
3 Execution timed out 10037 ms 6744 KB Time limit exceeded
4 Execution timed out 10010 ms 6488 KB Time limit exceeded
5 Execution timed out 10045 ms 6744 KB Time limit exceeded
6 Runtime error 17 ms 16364 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 18 ms 16132 KB Execution killed with signal 11
12 Runtime error 17 ms 16092 KB Execution killed with signal 11
13 Incorrect 25 ms 12048 KB wrong parameter
14 Runtime error 18 ms 15980 KB Execution killed with signal 11
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 36 ms 16292 KB Execution killed with signal 11
17 Runtime error 30 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16620 KB Execution killed with signal 11
19 Incorrect 17 ms 11780 KB wrong parameter
20 Runtime error 41 ms 18896 KB Execution killed with signal 11
21 Incorrect 41 ms 14308 KB wrong parameter
22 Incorrect 26 ms 12012 KB wrong parameter
23 Runtime error 49 ms 19172 KB Execution killed with signal 11