| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1000621 | 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 pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i)
#define mask(i) ((1LL << (i)))
#define status(x, i) (((x) >> (i)) & 1)
#define set_on(x, i) ((x) | mask(i))
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'
#define int long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
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 , k;
vector<pii> edges[maxn];
int val[maxn];
int hight[maxn];
int parent[maxn][LOG+1];
void dfs(int u , int p)
{
for (pii v : edges[u])
if (v.fi != p)
{
parent[v.fi][0] = u;
hight[v.fi] = hight[u] + 1;
val[v.fi] = val[u] + v.se;
dfs(v.fi , u );
}
}
void prepare()
{
dfs(1 , 0);
hight[0] = -1;
for (int j=1 ; j<=LOG ; ++j)
for (int i=1 ; i<=n ; ++i)
parent[i][j] = parent[parent[i][j-1]][j-1];
}
int lca(int u , int v)
{
if (hight[u] < hight[v]) return lca(v , u);
for (int i=LOG ; i>=0 ; --i)
if (hight[parent[u][i]] >= hight[v]) u = parent[u][i];
if (u == v) return u;
for (int i=LOG ; i>=1 ; --i)
if (parent[u][i] != parent[v][i]) u = parent[u][i] , v = parent[v][i];
return parent[v][0];
}
int solve(int n , int k , int adj[][2] , int weights[])
{
if (k == 1) return 0;
for (int i=0 ; i<n-1 ; ++i)
{
int u , v , w ;
u = adj[i][0];
v = adj[i][1];
w = weights[i];
++u , ++v;
edges[u].push_back({v , w});
edges[v].push_back({u , w});
}
prepare();
int ans = INF;
for (int i=2 ; i<=n ; ++i)
for (int j=1 ; j<i ; ++j)
{
int l = lca(i , j);
if (val[i] + val[j] - 2*val[l] == k)
minimize(ans , hight[i] + hight[j] - 2 * hight[l]);
}
return ans;
}