| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 733431 | happypotato | Snowy Roads (JOI16_snowy) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "snowy.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
void Save(int place, int bit);
int Ask(int place);
const int mxN = 1000;
int n;
vector<pii> edge;
void InitAnya(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
edge.pb({A[i], B[i]});
}
}
vector<pair<int, pii>> adj[mxN]; // {node, {0/1, idx}}
int ans[mxN];
vector<int> key;
map<int, int> mp;
pii par[mxN];
int dfs(int u = 0, int pp = -1, int cur = 0) {
ans[u] = cur;
int res = 0;
for (pair<int, pii> &v : adj[u]) {
if (v.ff == pp) continue;
par[v.ff] = {u, v.ss.ss};
res = max(res, dfs(v.ff, u, cur + v.ss.ff) + 1);
}
if (res >= 10) {
key.pb(u);
res -= 10;
}
return res;
}
void Anya(int C[]) {
for (int i = 0; i < n; i++) {
adj[i].clear();
}
key.clear();
for (int i = 0; i < n - 1; i++) {
adj[edge[i].ff].pb({edge[i].ss, {C[i], i}});
adj[edge[i].ss].pb({edge[i].ff, {C[i], i}});
}
dfs();
for (int i = 0; i < n - 1; i++) {
Save(500 + i, C[i]);
}
assert(key.size() <= 50);
for (int i = 0; i < (int)(key.size()); i++) {
for (int j = 0; j < 10; j++) {
Save(i * 10 + j, bool(ans[key[i]] & (1 << j)));
}
}
}
void InitBoris(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].pb({B[i], {0, i}});
adj[B[i]].pb({A[i], {0, i}});
}
dfs();
mp[0] = -1;
for (int i = 0; i < (int)(key.size()); i++) {
mp[key[i]] = i;
}
}
int Boris(int city) {
int ans = 0;
while (mp.find(city) == mp.end()) {
ans += Ask(500 + par[city].ss);
city = par[city].ff;
}
if (city) {
for (int i = 0; i < 10; i++) {
ans += (Ask(mp[city] * 10 + i) << i);
}
}
return ans;
}