oj.uz

답안 #1061506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1061506 2024-08-16T10:05:10 Z thieunguyenhuy 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 161 ms 19212 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[j] = 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 16552 KB wrong parameter
2 Incorrect 2 ms 11272 KB wrong parameter
3 Runtime error 15 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11264 KB wrong parameter
5 Runtime error 16 ms 16136 KB Execution killed with signal 11
6 Runtime error 17 ms 16380 KB Execution killed with signal 11
7 Incorrect 25 ms 12012 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 13 ms 11524 KB wrong parameter
10 Incorrect 11 ms 11516 KB wrong parameter
11 Runtime error 16 ms 16008 KB Execution killed with signal 11
12 Runtime error 19 ms 16128 KB Execution killed with signal 11
13 Incorrect 27 ms 12028 KB wrong parameter
14 Incorrect 12 ms 11512 KB wrong parameter
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 31 ms 16364 KB Execution killed with signal 11
17 Runtime error 26 ms 16388 KB Execution killed with signal 11
18 Runtime error 34 ms 16844 KB Execution killed with signal 6
19 Runtime error 20 ms 16252 KB Execution killed with signal 6
20 Runtime error 39 ms 18916 KB Execution killed with signal 11
21 Incorrect 44 ms 14504 KB wrong parameter
22 Incorrect 33 ms 11948 KB wrong parameter
23 Runtime error 61 ms 19212 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 16552 KB wrong parameter
2 Incorrect 2 ms 11272 KB wrong parameter
3 Runtime error 15 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11264 KB wrong parameter
5 Runtime error 16 ms 16136 KB Execution killed with signal 11
6 Runtime error 17 ms 16380 KB Execution killed with signal 11
7 Incorrect 25 ms 12012 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 13 ms 11524 KB wrong parameter
10 Incorrect 11 ms 11516 KB wrong parameter
11 Runtime error 16 ms 16008 KB Execution killed with signal 11
12 Runtime error 19 ms 16128 KB Execution killed with signal 11
13 Incorrect 27 ms 12028 KB wrong parameter
14 Incorrect 12 ms 11512 KB wrong parameter
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 31 ms 16364 KB Execution killed with signal 11
17 Runtime error 26 ms 16388 KB Execution killed with signal 11
18 Runtime error 34 ms 16844 KB Execution killed with signal 6
19 Runtime error 20 ms 16252 KB Execution killed with signal 6
20 Runtime error 39 ms 18916 KB Execution killed with signal 11
21 Incorrect 44 ms 14504 KB wrong parameter
22 Incorrect 33 ms 11948 KB wrong parameter
23 Runtime error 61 ms 19212 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 16552 KB wrong parameter
2 Incorrect 2 ms 11272 KB wrong parameter
3 Runtime error 15 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11264 KB wrong parameter
5 Runtime error 16 ms 16136 KB Execution killed with signal 11
6 Runtime error 17 ms 16380 KB Execution killed with signal 11
7 Incorrect 25 ms 12012 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 13 ms 11524 KB wrong parameter
10 Incorrect 11 ms 11516 KB wrong parameter
11 Runtime error 16 ms 16008 KB Execution killed with signal 11
12 Runtime error 19 ms 16128 KB Execution killed with signal 11
13 Incorrect 27 ms 12028 KB wrong parameter
14 Incorrect 12 ms 11512 KB wrong parameter
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 31 ms 16364 KB Execution killed with signal 11
17 Runtime error 26 ms 16388 KB Execution killed with signal 11
18 Runtime error 34 ms 16844 KB Execution killed with signal 6
19 Runtime error 20 ms 16252 KB Execution killed with signal 6
20 Runtime error 39 ms 18916 KB Execution killed with signal 11
21 Incorrect 44 ms 14504 KB wrong parameter
22 Incorrect 33 ms 11948 KB wrong parameter
23 Runtime error 61 ms 19212 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 16552 KB wrong parameter
2 Incorrect 2 ms 11272 KB wrong parameter
3 Runtime error 15 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11264 KB wrong parameter
5 Runtime error 16 ms 16136 KB Execution killed with signal 11
6 Runtime error 17 ms 16380 KB Execution killed with signal 11
7 Incorrect 25 ms 12012 KB wrong parameter
8 Runtime error 15 ms 16132 KB Execution killed with signal 11
9 Incorrect 13 ms 11524 KB wrong parameter
10 Incorrect 11 ms 11516 KB wrong parameter
11 Runtime error 16 ms 16008 KB Execution killed with signal 11
12 Runtime error 19 ms 16128 KB Execution killed with signal 11
13 Incorrect 27 ms 12028 KB wrong parameter
14 Incorrect 12 ms 11512 KB wrong parameter
15 Runtime error 16 ms 16128 KB Execution killed with signal 11
16 Runtime error 31 ms 16364 KB Execution killed with signal 11
17 Runtime error 26 ms 16388 KB Execution killed with signal 11
18 Runtime error 34 ms 16844 KB Execution killed with signal 6
19 Runtime error 20 ms 16252 KB Execution killed with signal 6
20 Runtime error 39 ms 18916 KB Execution killed with signal 11
21 Incorrect 44 ms 14504 KB wrong parameter
22 Incorrect 33 ms 11948 KB wrong parameter
23 Runtime error 61 ms 19212 KB Execution killed with signal 11