Submission #1017041

#TimeUsernameProblemLanguageResultExecution timeMemory
1017041MilosMilutinovicSaveit (IOI10_saveit)C++14
0 / 100
3056 ms262144 KiB
#include "grader.h" #include "encoder.h" #include <bits/stdc++.h> using namespace std; void encode(int nv, int nh, int ne, int *v1, int *v2) { vector<vector<int>> g(nv); for (int i = 0; i < ne; i++) { g[v1[i]].push_back(v2[i]); g[v2[i]].push_back(v1[i]); } vector<int> par(nv, -1); vector<bool> was(nv); function<void(int, int)> Dfs = [&](int v, int pv) { par[v] = pv; was[v] = true; for (int u : g[v]) { if (was[u]) { continue; } Dfs(u, v); } }; Dfs(0, 0); for (int v = 0; v < nv; v++) { for (int b = 0; b < 10; b++) { encode_bit(par[v] >> b & 1); } } for (int h = 0; h < nh; h++) { vector<int> dist(nv, -1); dist[h] = 0; vector<int> que(1, h); for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { if (dist[j] == -1) { dist[j] = dist[i] + 1; que.push_back(j); } } } for (int v = 0; v < nv; v++) { if (dist[v] == dist[par[v]]) { encode_bit(0); encode_bit(0); } if (dist[v] == dist[par[v]] + 1) { encode_bit(0); encode_bit(1); } if (dist[v] == dist[par[v]] - 1) { encode_bit(1); encode_bit(0); } } } return; }
#include "grader.h" #include "decoder.h" #include <bits/stdc++.h> using namespace std; void decode(int nv, int nh) { vector<int> par(nv); for (int v = 0; v < nv; v++) { for (int b = 0; b < 10; b++) { if (decode_bit()) { par[v] += (1 << b); } } } vector<vector<int>> ch(nv); for (int i = 1; i < nv; i++) { ch[par[i]].push_back(i); } for (int h = 0; h < nh; h++) { vector<int> d(nv); for (int v = 0; v < nv; v++) { int t = 0; t += 2 * decode_bit(); t += decode_bit(); d[v] = (t == 0 ? 0 : (t == 1 ? 1 : -1)); } vector<int> dist(nv, -1); dist[h] = 0; vector<int> que(1, h); for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : ch[i]) { dist[j] = dist[i] + d[i]; que.push_back(j); } if (dist[par[i]] == -1) { dist[par[i]] = dist[i] - d[i]; que.push_back(par[i]); } } for (int v = 0; v < nv; v++) { hops(h, v, dist[v]); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...