| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1193961 | steveonalex | Saveit (IOI10_saveit) | C++20 | 0 ms | 0 KiB |
/*
________ ___ ________ ________ ________ ___ ________ ________ ________
|\ ____\|\ \|\ ____\|\ __ \ |\ ___ \|\ \|\ ____\|\ ____\|\ __ \
\ \ \___|\ \ \ \ \___|\ \ \|\ \ \ \ \\ \ \ \ \ \ \___|\ \ \___|\ \ \|\ \
\ \ \ __\ \ \ \ \ __\ \ __ \ \ \ \\ \ \ \ \ \ \ __\ \ \ __\ \ __ \
\ \ \|\ \ \ \ \ \|\ \ \ \ \ \ \ \ \\ \ \ \ \ \ \|\ \ \ \|\ \ \ \ \ \
\ \_______\ \__\ \_______\ \__\ \__\ \ \__\\ \__\ \__\ \_______\ \_______\ \__\ \__\
\|_______|\|__|\|_______|\|__|\|__| \|__| \|__|\|__|\|_______|\|_______|\|__|\|__|
________ ________ ________ ________ ___ ___ ________ _________ ___ ________ ________
|\ __ \|\ __ \|\ __ \|\ ___ \|\ \|\ \|\ ____\\___ ___\\ \|\ __ \|\ ___ \
\ \ \|\ \ \ \|\ \ \ \|\ \ \ \_|\ \ \ \\\ \ \ \___\|___ \ \_\ \ \ \ \|\ \ \ \\ \ \
\ \ ____\ \ _ _\ \ \\\ \ \ \ \\ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \ \___|\ \ \\ \\ \ \\\ \ \ \_\\ \ \ \\\ \ \ \____ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \__\ \ \__\\ _\\ \_______\ \_______\ \_______\ \_______\ \ \__\ \ \__\ \_______\ \__\\ \__\
\|__| \|__|\|__|\|_______|\|_______|\|_______|\|_______| \|__| \|__|\|_______|\|__| \|__|
Written by: giga nigga
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
double wow = (double) ((ull) rng()) / ((ull)(0-1));
return wow * (r - l) + l;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "grader.h"
#include "encoder.h"
void encode(int n, int h, int m, int *U, int *V){
vector<vector<int>> graph(n);
for(int i = 0; i < m; ++i){
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
}
int dih[h][n];
vector<int> parent(n);
for(int i = 0; i < h; ++i){
vector<int> dis(n, 1023);
dis[i] = 0;
deque<int> q; q.push_back(i);
while(q.size()){
int u = q.front(); q.pop_front();
for(int v: graph[u]) if (minimize(dis[v], dis[u] + 1)){
q.push_back(v);
if (i == 0) parent[v] = u;
}
}
for(int j = 0; j < n; ++j) dih[i][j] = dis[j];
}
for(int j = 1; j < n; ++j){
for(int k = 0; k < 10; ++k) encode_bit(GETBIT(parent[j], k));
}
for(int i = 1; i < n; ++i){
ll po = 1, ans = 0;
for(int j = 0; j < h; ++j){
int cur = 0;
if (dih[j][parent[i]] == dih[j][i]) cur = 1;
else if (dih[j][parent[i]] > dih[j][i]) cur = 2;
ans += po * cur;
po *= 3;
}
for(int k = 0; k < 60; ++k) encode_bit(GETBIT(ans, k));
}
}
/*
________ ___ ________ ________ ________ ___ ________ ________ ________
|\ ____\|\ \|\ ____\|\ __ \ |\ ___ \|\ \|\ ____\|\ ____\|\ __ \
\ \ \___|\ \ \ \ \___|\ \ \|\ \ \ \ \\ \ \ \ \ \ \___|\ \ \___|\ \ \|\ \
\ \ \ __\ \ \ \ \ __\ \ __ \ \ \ \\ \ \ \ \ \ \ __\ \ \ __\ \ __ \
\ \ \|\ \ \ \ \ \|\ \ \ \ \ \ \ \ \\ \ \ \ \ \ \|\ \ \ \|\ \ \ \ \ \
\ \_______\ \__\ \_______\ \__\ \__\ \ \__\\ \__\ \__\ \_______\ \_______\ \__\ \__\
\|_______|\|__|\|_______|\|__|\|__| \|__| \|__|\|__|\|_______|\|_______|\|__|\|__|
________ ________ ________ ________ ___ ___ ________ _________ ___ ________ ________
|\ __ \|\ __ \|\ __ \|\ ___ \|\ \|\ \|\ ____\\___ ___\\ \|\ __ \|\ ___ \
\ \ \|\ \ \ \|\ \ \ \|\ \ \ \_|\ \ \ \\\ \ \ \___\|___ \ \_\ \ \ \ \|\ \ \ \\ \ \
\ \ ____\ \ _ _\ \ \\\ \ \ \ \\ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \ \___|\ \ \\ \\ \ \\\ \ \ \_\\ \ \ \\\ \ \ \____ \ \ \ \ \ \ \ \\\ \ \ \\ \ \
\ \__\ \ \__\\ _\\ \_______\ \_______\ \_______\ \_______\ \ \__\ \ \__\ \_______\ \__\\ \__\
\|__| \|__|\|__|\|_______|\|_______|\|_______|\|_______| \|__| \|__|\|_______|\|__| \|__|
Written by: giga nigga
*/
// #include "largest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
double wow = (double) ((ull) rng()) / ((ull)(0-1));
return wow * (r - l) + l;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "grader.h"
#include "decoder.h"
void dfs(int u, vector<vector<int>> &graph, vector<int> &ans){
ans.push_back(u);
for(int v: graph[u]) dfs(v, graph, ans);
}
vector<int> construct_dfs_order(int n, vector<int> parent){
vector<vector<int>> graph(n);
for(int i = 1; i < n; ++i) graph[parent[i]] = i;
vector<int> ans;
dfs(0, graph, ans);
return ans;
}
void decode(int n, int h){
vector<int> parent(n);
for(int j = 1; j < n; ++j){
for(int k = 0; k < 10; ++k) parent[j] += decode_bit() * MASK(k);
}
vector<int> order = construct_dfs_order(n, parent);
vector<ll> state(n);
for(int j = 1; j < n; ++j){
for(int k = 0; k < 60; ++k) state[j] += MASK(k) * decode_bit();
}
int ans[h][n]; memset(ans, 0, sizeof ans);
for(int i: order) if (i != 0){
for(int j = 0; j < h; ++j){
int cur = state[i] % 3;
state[i] /= 3;
if (cur == 0) ans[j][i] = ans[j][parent[i]] + 1;
else if (cur == 1) ans[j][i] = ans[j][parent[i]];
else ans[j][i] = ans[j][parent[i]] - 1;
}
}
for(int j = 0; j < h; ++j){
int mi = 0;
for(int i = 0; i < n; ++i) minimize(mi, ans[j][i]);
for(int i = 0; i < n; ++i) ans[j][i] -= mi;
for(int i = 0; i < n; ++i) hop(j, i, ans[j][i]);
}
}