| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 935721 | lftroq | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
:-=-
:%@@@@@@@@@=
.#@@@@@%@%@@@@@@=
-@@@@@@@@@@@@@@@@@#
.+@@@@@@@@@@@@@@@@@@@@.
#@@@@@@@@@@@@@@@@@@@@@%
.*@@@@@@@@@@@@@@@@@@@@@@@= ／￣￣￣￣￣￣￣￣￣＼
.@@@@@@@@@@@@@@@@@@@@@@@@# | lftroq ♥ |
+@@@@@@@@@@@%%@@@@@@@@@@@@- ＼＿＿＿＿＿＿＿＿＿／
.%@@@@@@@@@@%##%@@@@@@@@@@@# /／
-@@@@@@@@%%%%%%%%%@@@@@@@@@@:
-+- =@@@@@%##%#%##**+#@@@@@@@@@@-
.+++.%@@@%##%%%%%%%#**+##%%@@@@@@+
+=*%@@@#*###%%#=--+=+*##%@@@@@@%.
:*+%@@*+**##*=======+***#@@@@@@@:
=+++**%@###*=++=-==++**#@@@@@@@:
.**===*%@@@##+=**#*==***@@@@@@@@@:
:+++=+*+%%@@%#==+*%#*+=++@@@@@@@@%
.**#*+*+**+%#+=---=***+==*@@@@@@@:
:**#*+=+**@%##*%#++++--=++#@@@@@@@+-::.
=%**###**#@@%*=*%%%%%*==++++%@@@@@@#=-----.
.%@@%***###@@@%*++%%%#*===+=++++%@@@@%*=-----=.
=**##+=+##@@@@=+%+=***#%@#+**++++%@@%+=-------=:
.++===++====@@@@+--==-=#%%%%+++*++++#%+=------==+=.
-++--=++-:::::=#@#----+--*%%*+**+++++++==-----===--+=
:*+=--++-::::::--=-----==-=%==+%%***++=---=---===-=++:
:*+--+=-::::::::---:----+=-=++##***===-::::-+----=*+:
.=--:::.:::-=-::---::--------++--=====-::::--:-==++
:=::::::--::::::--=+-:--++++==++--==:::-:::----==+=
*-:::::::.....:-++++++++++++++=+=---::::===-:------
:+:--:......:-+++++++++++++++++====---:--=-=----:-:=.
:==--:::.:=+++++++++++++++++++++-::===-:-===-----=--:
.+=--:::-:=+++++==++++++++++++++=--:.:-===+-------+=-.
.+==-----::-+++-:+++=====+++++++=--=======--:----==+=.
:+===-----------:-++====+++++++++=--==--+-:------==-::
+=====-::----+-::-+====+++++++++++=---==:-===:-==-==.
:+===========+-::::-----+++++++++++*=--======-=+=-=.
.=========++=-::::::----:::-++++++*+=+======+++==.
.=========-::::::-----:::=+++++**+=+**====-:. .
*======-::::::::-:-----++++++++==++++++-
#======-:::::::::-------++++++++====+++=
=======-:::::::::----:::=+++++++=====+++
=====---:::::::::::------=++++++===+==++=
:===-:--:::::::::::-------+++++++===++=++
.===-:--:::::::::::::-----=+++++====++===.
.+=-::--::::::::::::-:-----++++++====++=+:
.=-:::--::::::::::::-------=+++++===-----+=
.=-:::--:::::::::::---------=++++==-----==+=.
.=-:::---:::::::::::---------+++===-----===++.
.=::::---:::::::-:-----------=++==-:-----===+-
.--:::---:::::::--------------=+=----==--===+-
.=::::---::::::::::-------===--==-------=--==:
.=--::--::::----:---:::::-:----:::-----======-
.=---:--:::---::::::--------------------==++++
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007LL
#define MOD2 998244353LL
#define endl '\n'
#define PI acos(-1)
#define INFINITE 2147483647LL
#define INFINITE2 9223372036854775807
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
#define sqrt sqrtl
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
ll n,k,ans=INFINITE;
vector<llll> graph[200005];
map<ll,ll> m[200005];
ll h[200005],c[200005];
void dfs(int u,int p)
{
ll t=k+2*c[u];
for(int i=0;i<(int)graph[u].size();i++)
{
ll v=graph[u][i].fi,w=graph[u][i].se;
if(v==p) continue;
h[v]=h[u]+1;
c[v]=c[u]+w;
m[v][c[v]]=h[v];
dfs(v,u);
if(m[v].size()>m[u].size()) swap(m[u],m[v]);
for(map<ll,ll>::iterator it=m[v].begin();it!=m[v].end();it++) if(m[u].find(t-it->fi)!=m[u].end()) ans=min(ans,m[u][t-it->fi]+it->se-2*h[u]);
for(map<ll,ll>::iterator it=m[v].begin();it!=m[v].end();it++) if(m[u].find(it->fi)!=m[u].end()) m[u][it->fi]=min(m[u][it->fi],it->se); else m[u][it->fi]=it->se;
}
}
ll best_path(ll n,ll k,ll edges[][2],ll weights[])
{
for(int i=0;i<n;i++)
{
ll u,v,w;
u=edges[i][0];
v=edges[i][1];
u++;v++;
w=weights[i];
graph[u].push_back({v,w});
graph[v].push_back({u,w});
}
dfs(1,1);
if(ans==INFINITE) ans=-1;
if(k==1) ans=0;
return ans;
}