| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 99408 | naoai | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 2e5;
static i64 K;
static int ans;
bool viz[nmax + 1];
int lant[nmax + 1], sz[nmax + 1];
i64 ct[nmax + 1];
vector<pair<int, int>> g[nmax + 1];
set<pair<i64, int>> s[nmax + 1];
void dfs (int nod, int h, int dad = -1) {
viz[nod] = 1;
sz[nod] = 1;
int mxf = -1, mxg = -1, valm = 0;
for (auto i : g[nod]) {
if (viz[i.first] == 0) {
dfs(i.first, h + 1, nod);
sz[nod] += sz[i.first];
if (sz[i.first] > mxg) {
mxg = sz[i.first];
mxf = i.first;
valm = i.second;
}
}
}
if (mxf == -1) {
lant[nod] = nod;
} else {
lant[nod] = lant[mxf];
}
ct[lant[nod]] += valm;
set<pair<i64, int>>::iterator it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - 0, 0});
if (it != s[lant[nod]].end() && (it -> first) == K - ct[lant[nod]]) {
ans = min(ans, (it -> second) - h);
}
s[lant[nod]].insert({0, h});
for (auto i : g[nod]) {
if (i.first == mxf || i.first == dad)
continue;
int l = lant[i.first];
ct[l] += i.second;
while (!s[l].empty()) {
pair<i64, int> x = *s[l].begin();
s[l].erase(s[l].begin());
x.first += ct[l];
it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - x.first, 0});
if (it != s[lant[nod]].end() && (it -> first) == K - ct[lant[nod]] - x.first) {
ans = min(ans, x.second + (it -> second) - 2 * h);
}
s[lant[nod]].insert({x.first - ct[lant[nod]], x.second});
}
}
}
int best_path (int n, i64 k, int h[nmax + 1][2], int l[nmax + 1]) {
K = k;
for (int i = 0; i < n - 1; ++ i) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
ans = n + 1;
dfs(0, 0);
++ ans;
if (ans == n + 2)
ans = -1;
return ans;
}
/*int main() {
int a[2][2]= {{0, 1}, {1, 2}};
int b[2] = {1, 1};
cout << best_path (3, 3, a, b) << "\n";
return 0;
}*/