| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 838867 | Shreyan_Paliwal | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>
string tostr(const T& value) {
ostringstream oss;
oss << value;
return oss.str();
}
template<typename... Args>
string fstr(const string& format, Args... args) {
string result = format;
size_t pos = 0;
size_t argIndex = 0;
auto replaceArg = [&](const auto& arg) {
pos = result.find("{}", pos);
if (pos != string::npos) {
result.replace(pos, 2, tostr(arg));
++argIndex;
}
};
(replaceArg(args), ...);
return result;
}
template<int SZ> struct Tree {
int n;
vector<pair<int,int>> adj[SZ];
void init(int N, int H[][2], int L[]) {
n = N;
for (int i = 0; i < n-1; i++) {
int a, b, c; cin >> a >> b >> c;
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
}
};
const int maxn = 200000;
int n, k;
int sz[maxn], dpth[maxn], ldpth[maxn];
Tree<maxn> tree;
unordered_map<int,int> m[maxn];
int ans = INT_MAX;
int dfs(int nd, int par, int l) {
sz[nd] = 1, dpth[nd] = dpth[par] + 1; ldpth[nd] = l;
for (auto i : tree.adj[nd])
if (i.first != par)
sz[nd] += dfs(i.first, nd, l + i.second);
return sz[nd];
}
inline int mget(int nd, int dist) {
// dist to find = ldist[nd] + dist;
dist += ldpth[nd];
if (m[nd].find(dist) == m[nd].end()) return INT_MAX;
return m[nd][dist];
}
inline void upd_min(int nd, int k, int v) {
if (m[nd].find(k) == m[nd].end()) {m[nd][k] = v; return; }
// cout << "Y " << nd << ' ' << k << ' ' << (m[nd].find(k) == m[nd].end()) << ' ' << m[nd][k] << ' ';
m[nd][k] = min(m[nd][k], v);
// cout << m[nd][k] << endl;
}
void msl(int nd, int par) {
for (auto i : tree.adj[nd])
if (i.first != par)
msl(i.first, nd);
int hch = -1, hb = -1;
for (auto i : tree.adj[nd])
if (i.first != par)
if (hch == -1 || hb < sz[i.first])
hch = i.first, hb = sz[i.first];
// cout << "Z " << nd << ' ' << (hch == -1) << endl;
if (hch == -1) {m[nd][ldpth[nd]] = dpth[nd];
// cout << "---------" << endl << nd << endl;
// cout << "X ";
// for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
// cout << endl;
return;}
// cout << "----" << endl;
swap(m[nd], m[hch]);
// cout << nd << endl;
for (auto i : tree.adj[nd])
if (i.first != par && i.first != hch)
for (auto j : m[i.first]) {
// cout << j.first << ' ' << j.second << endl;
// (dist[i], dpth[i]) --> (dist[i] - dist[nd], dpth[i] - dpth[nd])
int val = mget(nd, k - (j.first - ldpth[nd]));
if (val != INT_MAX)
ans = min(ans, j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd]);
// if (val != INT_MAX)
// cout << nd << ' ' << j.first << ' ' << j.second << ' ' << j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd] << endl;
upd_min(nd, j.first, j.second);
}
// cout << nd << ' ' << mget(nd, k) - dpth[nd] << endl;
// cout << "X ";
// for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
// cout << endl;
ans = min(ans, mget(nd, k) - dpth[nd]);
upd_min(nd, ldpth[nd], dpth[nd]);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
tree.init(n, H, L);
dfs(0, 0, 0);
msl(0, 0);
return ans;
}
// #define LOCAL
// #define CODEFORCES
// signed main() {
// #ifndef LOCAL
// cin.tie(nullptr) -> ios::sync_with_stdio(false);
// #endif
// #ifdef LOCAL
// freopen("main.in", "r", stdin);
// #endif
// int t;
// #ifdef CODEFORCES
// cin >> t;
// #endif
// #ifndef CODEFORCES
// t=1;
// #endif
// while(t--) solve();
// return 0;
// }