이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
*/
#define inf 1000000009
#define MAXN 200005
vll g[MAXN];
bool centroid_marked[MAXN];
int subtree[MAXN], K, tmpans, ans;
map<ll,int> road;
int dfs_init(int a, int par)
{
subtree[a] = 1;
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
subtree[a] += dfs_init(bb.ff, a);
return subtree[a];
}
int getCentroid(int a, int par, int n)
{
bool is_centroid = (n - subtree[a] <= n/2);
int hvy = -1;
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
{
is_centroid = is_centroid && (subtree[bb.ff] <= n/2);
if(hvy == -1 || subtree[hvy] < subtree[bb.ff]) hvy = bb.ff;
}
if(is_centroid)
return a;
return getCentroid(hvy, a, n);
}
void calc(int a, int par, int dist, int lev)
{
if(road.find(dist) != road.end()) road[dist] = min(road[dist], lev); else road[dist] = lev;
if(road.find(K-dist) != road.end()) tmpans = min(tmpans, road[dist] + road[K - dist]);
// cout<<"\tin calc("<<a<<','<<par<<','<<dist<<','<<lev<<")\n";
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
calc(bb.ff, a, bb.ss + dist, lev+1);
}
void dcmp(int root)
{
road.clear();
road[0] = 0;
tmpans = inf;
int n = dfs_init(root, -1);
int cen = getCentroid(root, -1, n);
// cout<<"cen = "<<cen<<"\n";
calc(cen,-1,0,0);
// cout<<"here we have \n";
// for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
// cout<<"road["<<(it->ff)<<"] = "<<(it->ss)<<'\n';
centroid_marked[cen] = true;
ans = min(ans, tmpans);
for(pll bb : g[cen])
if(!centroid_marked[bb.ff])
dcmp(bb.ff);
// cout<<"tmpans = "<<tmpans<<'\n';
}
int best_path(int NN,int KK,int H[][2],int L[])
{
K = KK;
F0R(i, NN)
centroid_marked[i] = false;
F0R(i, NN-1)
g[H[i][1]].pb(mp(H[i][0], L[i])), g[H[i][0]].pb(mp(H[i][1], L[i]));
ans = inf;
dcmp(0);
return (ans == inf) ? -1 : ans;
}
/*
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, KK;
cin>>N>>KK;
int H[N-1][2], L[N-1];
F0R(i, N-1)
cin>>H[i][0]>>H[i][1]>>L[i];
cout<<best_path(N, KK, H, L);
return 0;
}
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |