oj.uz

Submission #1061446

# Submission time Handle Problem Language Result Execution time Memory
1061446 2024-08-16T09:08:05 Z thieunguyenhuy Saveit (IOI10_saveit) C++17
0 / 100
 151 ms 21188 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];

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));
	}

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

#ifdef hwe
signed main() {


    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 151 ms 21188 KB Execution killed with signal 11
2 Incorrect 2 ms 11276 KB Output isn't correct
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 16 ms 16140 KB Execution killed with signal 11
7 Incorrect 23 ms 12024 KB wrong parameter
8 Runtime error 16 ms 16132 KB Execution killed with signal 11
9 Incorrect 11 ms 11780 KB wrong parameter
10 Runtime error 15 ms 16028 KB Execution killed with signal 11
11 Runtime error 18 ms 15948 KB Execution killed with signal 11
12 Runtime error 18 ms 16148 KB Execution killed with signal 11
13 Incorrect 35 ms 11948 KB wrong parameter
14 Runtime error 15 ms 16028 KB Execution killed with signal 11
15 Runtime error 16 ms 16132 KB Execution killed with signal 11
16 Runtime error 29 ms 16620 KB Execution killed with signal 11
17 Runtime error 34 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16496 KB Execution killed with signal 11
19 Incorrect 18 ms 11776 KB wrong parameter
20 Runtime error 48 ms 18852 KB Execution killed with signal 11
21 Incorrect 39 ms 14308 KB wrong parameter
22 Incorrect 25 ms 12028 KB wrong parameter
23 Runtime error 53 ms 19220 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 21188 KB Execution killed with signal 11
2 Incorrect 2 ms 11276 KB Output isn't correct
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 16 ms 16140 KB Execution killed with signal 11
7 Incorrect 23 ms 12024 KB wrong parameter
8 Runtime error 16 ms 16132 KB Execution killed with signal 11
9 Incorrect 11 ms 11780 KB wrong parameter
10 Runtime error 15 ms 16028 KB Execution killed with signal 11
11 Runtime error 18 ms 15948 KB Execution killed with signal 11
12 Runtime error 18 ms 16148 KB Execution killed with signal 11
13 Incorrect 35 ms 11948 KB wrong parameter
14 Runtime error 15 ms 16028 KB Execution killed with signal 11
15 Runtime error 16 ms 16132 KB Execution killed with signal 11
16 Runtime error 29 ms 16620 KB Execution killed with signal 11
17 Runtime error 34 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16496 KB Execution killed with signal 11
19 Incorrect 18 ms 11776 KB wrong parameter
20 Runtime error 48 ms 18852 KB Execution killed with signal 11
21 Incorrect 39 ms 14308 KB wrong parameter
22 Incorrect 25 ms 12028 KB wrong parameter
23 Runtime error 53 ms 19220 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 21188 KB Execution killed with signal 11
2 Incorrect 2 ms 11276 KB Output isn't correct
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 16 ms 16140 KB Execution killed with signal 11
7 Incorrect 23 ms 12024 KB wrong parameter
8 Runtime error 16 ms 16132 KB Execution killed with signal 11
9 Incorrect 11 ms 11780 KB wrong parameter
10 Runtime error 15 ms 16028 KB Execution killed with signal 11
11 Runtime error 18 ms 15948 KB Execution killed with signal 11
12 Runtime error 18 ms 16148 KB Execution killed with signal 11
13 Incorrect 35 ms 11948 KB wrong parameter
14 Runtime error 15 ms 16028 KB Execution killed with signal 11
15 Runtime error 16 ms 16132 KB Execution killed with signal 11
16 Runtime error 29 ms 16620 KB Execution killed with signal 11
17 Runtime error 34 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16496 KB Execution killed with signal 11
19 Incorrect 18 ms 11776 KB wrong parameter
20 Runtime error 48 ms 18852 KB Execution killed with signal 11
21 Incorrect 39 ms 14308 KB wrong parameter
22 Incorrect 25 ms 12028 KB wrong parameter
23 Runtime error 53 ms 19220 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 21188 KB Execution killed with signal 11
2 Incorrect 2 ms 11276 KB Output isn't correct
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 15 ms 16124 KB Execution killed with signal 11
6 Runtime error 16 ms 16140 KB Execution killed with signal 11
7 Incorrect 23 ms 12024 KB wrong parameter
8 Runtime error 16 ms 16132 KB Execution killed with signal 11
9 Incorrect 11 ms 11780 KB wrong parameter
10 Runtime error 15 ms 16028 KB Execution killed with signal 11
11 Runtime error 18 ms 15948 KB Execution killed with signal 11
12 Runtime error 18 ms 16148 KB Execution killed with signal 11
13 Incorrect 35 ms 11948 KB wrong parameter
14 Runtime error 15 ms 16028 KB Execution killed with signal 11
15 Runtime error 16 ms 16132 KB Execution killed with signal 11
16 Runtime error 29 ms 16620 KB Execution killed with signal 11
17 Runtime error 34 ms 16364 KB Execution killed with signal 11
18 Runtime error 32 ms 16496 KB Execution killed with signal 11
19 Incorrect 18 ms 11776 KB wrong parameter
20 Runtime error 48 ms 18852 KB Execution killed with signal 11
21 Incorrect 39 ms 14308 KB wrong parameter
22 Incorrect 25 ms 12028 KB wrong parameter
23 Runtime error 53 ms 19220 KB Execution killed with signal 11