| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 449395 | vishalagrawal | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define endl "\n"
#define int long long
#define double long double
#define precise(x) \
fixed << setprecision(x)
#ifndef ONLINE_JUDGE
#define debug(var) cerr << (#var) << ": " << var << endl
#else
#define debug(var)
#endif
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T>;
template <class T>
ostream &operator<<(ostream &os, min_heap<T> H)
{
while (!H.empty())
{
os << H.top() << " ";
H.pop();
}
os << endl;
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, max_heap<T> H)
{
while (!H.empty())
{
os << H.top() << " ";
H.pop();
}
os << endl;
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
return os << P.first << " " << P.second;
}
template <class T>
ostream &operator<<(ostream &os, vector<T> arr)
{
for (int i = 0; i < (int)arr.size(); i++)
{
os << arr[i] << " ";
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> matrix)
{
os << endl;
for (int i = 0; i < (int)matrix.size(); i++)
{
for (int j = 0; j < (int)matrix[i].size(); j++)
{
os << matrix[i][j] << " ";
}
os << endl;
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
for (auto s : S)
{
os << s << " ";
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, multiset<T> S)
{
for (auto s : S)
{
os << s << " ";
}
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
os << endl;
for (auto m : M)
{
os << m << endl;
}
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, multimap<L, R> M)
{
os << endl;
for (auto m : M)
{
os << m << endl;
}
return os << "";
}
const int max_n = 2e5 + 10;
vector<vector<int>> adj;
vector<vector<pair<int, int>>> g;
map<int, multiset<int>> vals;
int depth[max_n];
int arr[max_n];
int sz[max_n];
int heavy = -1;
int K;
int ans = 1e9;
int sack_size(int node, int cur_depth, int cur, int parent = 0)
{
arr[node] = cur;
depth[node] = cur_depth;
sz[node] = 1;
int max_sz = 0;
for (int i = 0; i < (int)g[node].size(); i++)
{
if (g[node][i].first == parent)
{
continue;
}
int temp = sack_size(g[node][i].first, cur_depth + 1, cur + g[node][i].second, node);
sz[node] += temp;
if (temp > max_sz)
{
max_sz = temp;
swap(adj[node][0], adj[node][i]);
}
}
return sz[node];
}
void sack_add(int node, int parent, int root, int type)
{
if (type == 0)
{
vals[arr[node]].erase(vals[arr[node]].find(depth[node]));
}
else
{
int need = K - arr[node] + 2 * arr[root];
if (vals[need].size() != 0)
{
ans = min(ans, *vals[need].begin() + depth[node] - 2 * depth[root]);
}
vals[arr[node]].insert(depth[node]);
}
for (int i = 0; i < (int)adj[node].size(); i++)
{
if (adj[node][i] != parent && adj[node][i] != heavy)
{
sack_add(adj[node][i], node, root, type);
}
}
}
void sack_dfs(int node, int parent, int keep)
{
for (int i = 1; i < (int)adj[node].size(); i++)
{
if (adj[node][i] != parent)
{
sack_dfs(adj[node][i], node, 0);
}
}
if (sz[node] != 1)
{
sack_dfs(adj[node][0], node, 1);
heavy = adj[node][0];
}
sack_add(node, parent, node, 1);
heavy = -1;
if (!keep)
{
sack_add(node, parent, node, 0);
}
}
int best_path(int temp_N, int temp_K, int* edge[2], int* L)
{
int N = temp_N;
K = temp_K;
for (int i = 0; i < N - 1; i++)
{
edge[i][0]++;
edge[i][1]++;
}
g.resize(N + 1);
adj.resize(N + 1);
for (int i = 0; i < N - 1; i++)
{
int weight = L[i];
g[edge[i][0]].push_back({edge[i][1], weight});
g[edge[i][1]].push_back({edge[i][0], weight});
adj[edge[i][0]].push_back(edge[i][1]);
adj[edge[i][1]].push_back(edge[i][0]);
}
sack_size(1, 1, 1);
sack_dfs(1, 0, 0);
if (ans == 1e9)
{
return -1;
}
return ans;
}