| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 300539 | mode149256 | City (JOI17_city) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*input
*/
#include <bits/stdc++.h>
#include "Device.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;
vi lens2;
void genLens2() {
double R = 1.05;
int cur = 1;
while (cur < 180 * MX) {
lens2.emplace_back(cur);
cur = max(cur + 1, (int)round(R * cur));
}
}
void InitDevice()
{
genLens2();
}
int Answer(ll S, ll T)
{
int sx = S / lens2.size();
int sy = T / lens2.size();
int xlen = lens2[S % lens2.size()];
int ylen = lens2[T % lens2.size()];
// printf("S = %d, st = %d, ilgis = %d\n", S, sx, xlen);
// printf("T = %d, st = %d, ilgis = %d\n", S, sy, ylen);
if (sx <= sy and sy + ylen <= sx + xlen) return 1;
else if (sy <= sx and sx + xlen <= sy + ylen) return 0;
else return 2;
}
/*input
*/
#include <bits/stdc++.h>
#include "Encoder.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;
vi lens1;
int n;
vii edges(MX);
int piv = 0;
vi st(MX);
vi ilgis(MX);
void genLens1() {
double R = 1.05;
int cur = 1;
while (cur < 180 * MX) {
lens1.emplace_back(cur);
cur = max(cur + 1, (int)round(R * cur));
}
}
void dfs(int x, int p) {
st[x] = piv++;
for (auto u : edges[x]) {
if (u != p)
dfs(u, x);
}
int ind = lower_bound(lens1.begin(), lens1.end(), piv - st[x]) - lens1.begin();
piv = st[x] + lens1[ind];
ilgis[x] = ind;
}
void Encode(int N, int A[], int B[])
{
n = N;
genLens1();
for (int i = 0; i < N - 1; ++i)
{
edges[A[i]].emplace_back(B[i]);
edges[B[i]].emplace_back(A[i]);
}
dfs(0, -1);
for (int i = 0; i < N; ++i) {
// printf("i = %d, code = %lld, st = %d, ilgis = %d\n", i, (ll)st[i]*lens1.size() + ilgis[i], st[i], lens1[ilgis[i]]);
Code(i, (ll)st[i]*lens1.size() + ilgis[i]);
}
}