| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1087795 | nmts | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define endl '\n'
#define ll long long
#define int ll
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
template <class T> inline T sqr(T x) { return x * x; };
template <class T> inline int Power(T x, int y)
{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
inline int gcd(int x, int y)
{ return y ? gcd(y , x % y) : x;}
inline int lcm(int x, int y) { return x * y / gcd(x, y); }
using namespace std;
int n;
int ans = INF;
vector<pii> edges[maxn];
int k;
int cnt[maxn];
struct CD{
int sz[maxn];
bool del[maxn];
int dfs(int u , int p)
{
sz[u] = 1;
for (auto&[v , w] : edges[u])
if (v != p && del[v] == 0)
sz[u] += dfs(v , u);
return sz[u];
}
int find_centroid(int u , int p , int total)
{
for (auto&[v , w] : edges[u])
if (v != p && del[v] == 0 && sz[v] > total / 2)
return find_centroid(v ,u , total);
return u;
}
void calc(int u , int p, int l , int h , int t)
{
if (l > k) return;
if (t == 0)
{
minimize(ans , cnt[k - l] + h);
// cout << l << " " << cnt[k - l] + h << endl;
}
else if (t == 1) cnt[l] = min(cnt[l] , h);
else cnt[l] = INF + INF;
for (auto&[v , w]: edges[u])
if (v != p && del[v] == 0)
calc(v , u , l + w , h + 1 , t);
}
void decompose(int u )
{
u = find_centroid(u , 0 , dfs(u , 0));
del[u] = 1;
// cerr << u << endl;
for (auto&[v , w] : edges[u])
if (del[v] == 0)
{
calc(v , u , w , 1 , 0);
calc(v , u , w , 1 , 1);
}
for (auto&[v ,w] : edges[u])
if (del[v] == 0)
calc(v , u , w , 1 , -1);
for (auto&[v , w]: edges[u] )
if (del[v] == 0)
{
decompose(v);
}
}
} cd;
// void solve()
// {
// cin >> n >> k;
// for (int i = 1 ; i < n ; ++i)
// {
// int u , v , w; cin >> u >> v >> w;
// ++u , ++v;
// edges[u].push_back({v , w});
// edges[v].push_back({u , w});
// }
// memset(cnt , INF + INF , sizeof cnt);
// cnt[0] = 0;
// cd.decompose(1);
// cout << (ans >= INF ? -1 : ans) << endl;
// }
int best_path(int _n, int _k, int H[][2], int l[])
{
n = _n;
k = _k;
memset(cnt , INF + INF , sizeof cnt);
cnt[0] = 0;
for (int i = 0; i < n - 1; i++)
{
int w = l[i];
int u = H[i][0]++, v = H[i][1]++;
edges[u].push_back({v, w});
edges[v].push_back({u, w});
}
cd.decompose(1);
return (ans >= INF ? -1 : ans);
}
// int32_t main()
// {
// faster;
// // file("txt");
// // int t ; cin >> t ; while (t--)
// solve();
// return 0;
// }