| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1257618 | makrav | City (JOI17_city) | C++20 | 0 ms | 0 KiB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
void Encode(int N, int A[], int B[])
{
vector<vector<int>> g(N);
for (int i = 0; i < N - 1; i++) {
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
vector<int> sub(N);
vector<vector<int>> g2(N);
auto dfs = [&](int v, int p, auto&&self) -> void {
sub[v] = 1;
for (int u : g[v]) {
if (u != p) {
g2[v].pb(u);
self(u, v, self);
sub[v] += sub[u];
}
}
};
dfs(0, 0, dfs);
auto sol = [&](vector<int> roots, int h, ll code, auto&&self) -> void {
// ?for (int u : roots) cout << u << ' ';
// cout << h << ' ' << code << '\n';
if (roots.empty()) return;
vector<int> r2;
if (roots.size() == 1) {
//cout << "enc " << roots[0] << ' ' << (1ll << h) + code << '\n';
Code(roots[0], (1ll << h) + code);
for (int u : g2[roots[0]]) {
r2.pb(u);
}
} else {
r2 = roots;
}
if (r2.empty()) return;
sort(all(r2), [&](int x, int y) {
return sub[x] > sub[y];
});
if (sub[r2[0]] == 1) {
for (int u : r2[0]) {
Code(u, (1ll << (h + 1)) + code);
}
return;
}
int ts = 0, cts = 0;
for (int u : r2) ts += sub[u];
for (int j = 0; j < sz(r2); j++) {
cts += sub[r2[j]];
if (cts >= ts / 2) {
vector<int> fr, sc;
for (int jj = 0; jj <= j; jj++) fr.pb(r2[jj]);
for (int jj = j + 1; jj < sz(r2); jj++) sc.pb(r2[jj]);
self(fr, h + 1, code, self);
self(sc, h + 1, code + (1ll << h), self);
break;
}
}
};
sol({0}, 0, 0, sol);
}
#include "Device.h"
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
if (S == T) return 2;
ll H1 = 63 - __builtin_clzll(S), H2 = 63 - __builtin_clzll(T);
S -= (1ll << H1); T -= (1ll << H2);
//cout << H1 << ' ' << H2 << ' ' << S << ' ' << T << '\n';
if (H1 == H2) return 2;
if (H1 < H2) {
if ((T % (1ll << H1)) == S) return 1;
return 2;
} else {
if ((S % (1ll << H2)) == T) return 0;
return 2;
}
// if ((S&T) != std::min(S, T)) return 2;
// if (H1 < H2) return 1;
// return 0;
}