oj.uz

답안 #1061447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1061447 2024-08-16T09:08:48 Z thieunguyenhuy 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 149 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 + 3, 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 21188 KB Execution killed with signal 11
2 Incorrect 1 ms 11268 KB Output isn't correct
3 Runtime error 14 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 16 ms 16132 KB Execution killed with signal 11
6 Runtime error 17 ms 16136 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16112 KB Execution killed with signal 11
9 Incorrect 16 ms 11524 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 17 ms 16132 KB Execution killed with signal 11
12 Runtime error 15 ms 16096 KB Execution killed with signal 11
13 Incorrect 28 ms 11896 KB wrong parameter
14 Runtime error 15 ms 16132 KB Execution killed with signal 11
15 Runtime error 17 ms 16112 KB Execution killed with signal 11
16 Runtime error 29 ms 16388 KB Execution killed with signal 11
17 Runtime error 27 ms 16356 KB Execution killed with signal 11
18 Runtime error 32 ms 16748 KB Execution killed with signal 11
19 Incorrect 20 ms 11784 KB wrong parameter
20 Runtime error 41 ms 18796 KB Execution killed with signal 11
21 Incorrect 53 ms 14556 KB wrong parameter
22 Incorrect 25 ms 12036 KB wrong parameter
23 Runtime error 49 ms 19112 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 21188 KB Execution killed with signal 11
2 Incorrect 1 ms 11268 KB Output isn't correct
3 Runtime error 14 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 16 ms 16132 KB Execution killed with signal 11
6 Runtime error 17 ms 16136 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16112 KB Execution killed with signal 11
9 Incorrect 16 ms 11524 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 17 ms 16132 KB Execution killed with signal 11
12 Runtime error 15 ms 16096 KB Execution killed with signal 11
13 Incorrect 28 ms 11896 KB wrong parameter
14 Runtime error 15 ms 16132 KB Execution killed with signal 11
15 Runtime error 17 ms 16112 KB Execution killed with signal 11
16 Runtime error 29 ms 16388 KB Execution killed with signal 11
17 Runtime error 27 ms 16356 KB Execution killed with signal 11
18 Runtime error 32 ms 16748 KB Execution killed with signal 11
19 Incorrect 20 ms 11784 KB wrong parameter
20 Runtime error 41 ms 18796 KB Execution killed with signal 11
21 Incorrect 53 ms 14556 KB wrong parameter
22 Incorrect 25 ms 12036 KB wrong parameter
23 Runtime error 49 ms 19112 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 21188 KB Execution killed with signal 11
2 Incorrect 1 ms 11268 KB Output isn't correct
3 Runtime error 14 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 16 ms 16132 KB Execution killed with signal 11
6 Runtime error 17 ms 16136 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16112 KB Execution killed with signal 11
9 Incorrect 16 ms 11524 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 17 ms 16132 KB Execution killed with signal 11
12 Runtime error 15 ms 16096 KB Execution killed with signal 11
13 Incorrect 28 ms 11896 KB wrong parameter
14 Runtime error 15 ms 16132 KB Execution killed with signal 11
15 Runtime error 17 ms 16112 KB Execution killed with signal 11
16 Runtime error 29 ms 16388 KB Execution killed with signal 11
17 Runtime error 27 ms 16356 KB Execution killed with signal 11
18 Runtime error 32 ms 16748 KB Execution killed with signal 11
19 Incorrect 20 ms 11784 KB wrong parameter
20 Runtime error 41 ms 18796 KB Execution killed with signal 11
21 Incorrect 53 ms 14556 KB wrong parameter
22 Incorrect 25 ms 12036 KB wrong parameter
23 Runtime error 49 ms 19112 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 21188 KB Execution killed with signal 11
2 Incorrect 1 ms 11268 KB Output isn't correct
3 Runtime error 14 ms 16132 KB Execution killed with signal 11
4 Incorrect 1 ms 11268 KB wrong parameter
5 Runtime error 16 ms 16132 KB Execution killed with signal 11
6 Runtime error 17 ms 16136 KB Execution killed with signal 11
7 Incorrect 22 ms 12000 KB wrong parameter
8 Runtime error 15 ms 16112 KB Execution killed with signal 11
9 Incorrect 16 ms 11524 KB wrong parameter
10 Runtime error 15 ms 16128 KB Execution killed with signal 11
11 Runtime error 17 ms 16132 KB Execution killed with signal 11
12 Runtime error 15 ms 16096 KB Execution killed with signal 11
13 Incorrect 28 ms 11896 KB wrong parameter
14 Runtime error 15 ms 16132 KB Execution killed with signal 11
15 Runtime error 17 ms 16112 KB Execution killed with signal 11
16 Runtime error 29 ms 16388 KB Execution killed with signal 11
17 Runtime error 27 ms 16356 KB Execution killed with signal 11
18 Runtime error 32 ms 16748 KB Execution killed with signal 11
19 Incorrect 20 ms 11784 KB wrong parameter
20 Runtime error 41 ms 18796 KB Execution killed with signal 11
21 Incorrect 53 ms 14556 KB wrong parameter
22 Incorrect 25 ms 12036 KB wrong parameter
23 Runtime error 49 ms 19112 KB Execution killed with signal 11