| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 237120 | mode149256 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*input
*/
#include <bits/stdc++.h>
#include "race.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 = 200101;
const int DID = 1e6;
vb buvau(MX, false);
queue<int> toliau;
vi sz(MX);
int piv;
vi edges[MX];
vi len[MX];
int ats = MOD;
vpi pir(DID + 1, {MOD, -1});
vpi ant(DID + 1, {MOD, -1});
unordered_set<int> visi;
int update(int x, int p) {
piv++;
sz[x] = 1;
for (auto u : edges[x])
if (!buvau[u] and u != p)
sz[x] += update(u, x);
return sz[x];
}
void prid(int x, int p, int curr, int cnt, int origin) {
if (curr <= reik) {
visi.insert(curr);
if (pir[curr].y == origin) {
pir[curr].x = min(pir[curr].x, cnt);
} else if (ant[curr].y == origin) {
ant[curr].x = min(ant[curr].x, cnt);
if (ant[curr] < pir[curr])
swap(pir[curr], ant[curr]);
} else {
if (cnt <= pir[curr].x) {
ant[curr] = pir[curr];
pir[curr] = {cnt, origin};
} else if (cnt < ant[curr].x) {
ant[curr] = {cnt, origin};
}
}
}
for (int i = 0; i < (int)edges[x].size(); ++i)
{
int u = edges[x][i];
if (!buvau[u] and u != p)
prid(u, x, curr + len[x][i], cnt + 1, origin);
}
}
int reik;
void proccess(int x) {
visi.clear();
for (int i = 0; i < (int)edges[x].size(); ++i)
{
int u = edges[x][i];
if (!buvau[u])
prid(u, x, len[x][i], 1, u);
}
for (auto u : visi) {
if (u > reik) continue;
if (pir[u].y == -1 or pir[reik - u].y == -1) continue;
if (pir[u].y != pir[reik - u].y) {
// printf("u = %d, kit = %d, pir pir %d %d\n", u, reik - u, pir[u].x, pir[reik - u].x);
ats = min(ats, pir[u].x + pir[reik - u].x);
} else if (ant[reik - u].y != -1 and pir[u].y != ant[reik - u].y) {
// printf("u = %d, kit = %d, pir ant %d %d\n", u, reik - u, pir[u].x, ant[reik - u].x);
ats = min(ats, pir[u].x + ant[reik - u].x);
} else if (ant[u].y != -1 and ant[u].y != pir[reik - u].y) {
// printf("u = %d, kit = %d, ant pir %d %d\n", u, reik - u, ant[u].x, pir[reik - u].x);
ats = min(ats, ant[u].x + pir[reik - u].x);
}
// else if (ant[u].y != -1 and ant[reik - u].y != -1 and ant[u].y != ant[reik - u].y) {
// ats = min(ats, ant[u].x + ant[reik - u].x);
// }
}
for (auto u : visi) {
pir[u] = ant[u] = {MOD, -1};
}
// for (int i = 0; i < (int)edges[x].size(); ++i)
// {
// int u = edges[x][i];
// if (!buvau[u])
// prid(u, x, len[x][i], -1, u);
// }
}
void centroid(int x, int p, int dydis) {
for (auto u : edges[x]) {
if (!buvau[u] and u != p and sz[u] > dydis / 2) {
centroid(u, x, dydis);
return;
}
}
// x is centroid
proccess(x);
buvau[x] = true;
for (auto u : edges[x])
if (!buvau[u])
toliau.push(u);
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N - 1; ++i)
{
edges[H[i][0]].emplace_back(H[i][1]);
len[H[i][0]].emplace_back(L[i]);
edges[H[i][1]].emplace_back(H[i][0]);
len[H[i][1]].emplace_back(L[i]);
}
pir[0] = {0, -5};
reik = K;
toliau.push(0);
while (toliau.size()) {
int c = toliau.front(); toliau.pop();
piv = 0;
update(c, -1);
centroid(c, -1, piv);
}
if (ats == MOD) return -1;
else return ats;
}