이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
#define MOD 1000000007
using namespace std;
const int N = 200005;
const int K = 1000005;
map<int, bool> vis;
vector<pair<int, int>> adj[N];
vector<int> adj1[N];
int tb = 0;
int t = 0;
int tin[N], tout[N];
int depth[N], edges[N];
bool chosen[N];
int h[N][20];
int s[N], size = 0;
int ans = INF;
int LCA_DFS(int i, int par, int dep, int edep){
tin[i] = ++t;
depth[i] = dep;
edges[i] = edep;
if(i!=par){
h[i][0] = par;
for(int j = 1;j<=19;j++){
if(h[i][j-1] != -1) h[i][j] = h[h[i][j-1]][j-1];
}
}
for(pair<int, int> j: adj[i]){
if(j.first == par) continue;
LCA_DFS(j.first, i, dep + j.second, edep+1);
}
tout[i] = ++t;
}
bool anc(int u, int v){
if((tin[u] <= tin[v]) && (tout[u] >= tout[v])) return true;
return false;
}
int LCA(int u, int v){
if(anc(u, v)){
return u;
}
if(anc(v, u)) return v;
for(int i = 19;i>=0;i--){
if(h[u][i]!=-1 && !anc(h[u][i], v)) u = h[u][i];
}
return h[u][0];
}
pair<int, int> dist(int u, int v){
return {(depth[u] + depth[v] - 2*depth[LCA(u, v)]), (edges[u] + edges[v] - 2*edges[LCA(u, v)])};
}
int dfs(int i, int par){
size++;
s[i] = 1;
for(pair<int, int> j: adj[i]){
if(j.first == par) continue;
s[i] += dfs(j.first, i);
}
return s[i];
}
int centroid(int i, int par){
for(pair<int, int> j: adj[i]){
if(j.first == par) continue;
if(chosen[j.first]) continue;
if(s[j.first] <= (size/2)) continue;
return centroid(j.first, i);
}
return i;
}
int decompose(int i, int par){
size = 0;
dfs(i, par);
int pp = centroid(i, par);
chosen[pp] = true;
for(pair<int, int> j: adj[pp]){
if(chosen[j.first]) continue;
int child = decompose(j.first, pp);
//cout<<pp<<" is a parent of "<<child<<endl;
adj1[pp].push_back(child);
}
return pp;
}
int findans(int i, int src, int mine[]){
pair<int, int> d = dist(i, src);
if(d.first<=tb) if(vis[tb - d.first]) ans = min(ans, d.second + mine[tb - d.first]);
for(int j: adj1[i]){
findans(j, src, mine);
}
}
int update(int i, int src, int mine[]){
pair<int, int> d = dist(i, src);
//cout<<"Distance from "<<i<<" to "<<src<<" is "<<d.first<<endl;
if(d.first<=tb){
if(!vis[d.first]) mine[d.first] = d.second;
else mine[d.first] = min(mine[d.first], d.second);
vis[d.first] = true;
}
for(int j: adj1[i]){
update(j, src, mine);
}
}
int getans(int i, int mine[]){
for(int j: adj1[i]){
findans(j, i, mine);
update(j, i, mine);
}
}
signed best_path(signed n, signed k, signed hh[][2], signed l[]){
tb = k;
ans = INF;
for(int i = 0;i<(n-1);i++){
adj[hh[i][0]+1].push_back({hh[i][1]+1, l[i]});
adj[hh[i][1]+1].push_back({hh[i][0]+1, l[i]});
}
for(int i = 1;i<=n;i++){
for(int j = 0;j<20;j++) h[i][j] = -1;
}
LCA_DFS(1, 1, 0, 0);
int cr = decompose(1, 1);
//cr is the new root of our tree
for(int i = 1;i<=n;i++){
int mine[K];
vis.clear();
mine[0] = 0;
vis[0] = true;
getans(i, mine);
}
if(ans>=INF) ans = -1;
return ans;
}
/*signed main(){
signed n, k;
cin>>n>>k;
signed bitch[n-1][2];
signed l[n-1];
for(int i =0 ;i<(n-1);i++) cin>>bitch[i][0]>>bitch[i][1]>>l[i];
cout<<best_path(n, k, bitch, l)<<endl;
}*/
/*
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
*/
/*
3 3
0 1 1
1 2 1
*/
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'long long int LCA_DFS(long long int, long long int, long long int, long long int)':
race.cpp:44:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'long long int findans(long long int, long long int, long long int*)':
race.cpp:99:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'long long int update(long long int, long long int, long long int*)':
race.cpp:111:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'long long int getans(long long int, long long int*)':
race.cpp:117:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:129:9: warning: unused variable 'cr' [-Wunused-variable]
int cr = decompose(1, 1);
^~
# | 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... |