이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
#define DIMN 200010
#define MAX_N 500000
using namespace std;
vector < pair <int,int> > v[DIMN];
set < pair <long long,int> > per[DIMN];
int sub[DIMN] , f[DIMN] , distanta[DIMN];
long long add[DIMN];
int sol;
void precalc (int nod , int tt){
int i , vecin;
sub[nod] = 1;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt && !f[vecin]){
precalc (vecin , nod);
sub[nod] += sub[vecin];
}
}
}
void dfs (int nod , int tt , int k){
int i , vecin , maxi = 0 , fiu ;
long long rms;
set < pair <long long,int> > :: iterator aux;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt && sub[vecin] > maxi){
maxi = sub[vecin];
fiu = vecin;
}
}
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt){
dfs (vecin , nod , k);
add[vecin] += v[nod][i].second;
distanta[vecin]++;
}
}
if (maxi){
per[nod].swap(per[fiu]);
add[nod] = add[fiu];
distanta[nod] = distanta[fiu];
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt){
if (vecin != fiu){
rms = k - v[nod][i].second - add[nod];
aux = per[nod].upper_bound(make_pair(rms , -2000000000));
if (aux != per[nod].end() && aux->first == rms){
sol = min(sol , 1 + aux->second + distanta[nod]);
}
}
per[nod].insert(make_pair(v[nod][i].second - add[nod] , 1 - distanta[nod]));
}
if (vecin != tt && vecin != fiu){
/// sa zicem ca nod ar fi lca - ul , un capat pana acum , unul in vecin
for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
if (it->first + add[vecin] > k)
continue;
rms = k - (it->first + add[vecin]) - add[nod];
aux = per[nod].upper_bound(make_pair(rms , -2000000000));
if (aux != per[nod].end() && aux->first == rms){
sol = min(sol , it->second + distanta[vecin] + aux->second + distanta[nod]);
}
}
/// vezi cum le unesti
for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
if (it->first + add[vecin] > k)
continue; /// nu imi pasa
per[nod].insert(make_pair(it->first + add[vecin] - add[nod] , it->second + distanta[vecin] - distanta[nod]));
}
}
}
}
aux = per[nod].upper_bound(make_pair(k - add[nod] , -2000000000));
if (aux != per[nod].end() && aux->first == k - add[nod]){
sol = min(sol , aux->second + distanta[nod]);
}
}
int best_path(int n, int k, int h[][2], int l[]){
int i;
for (i = 0 ; i < n - 1 ; i++){
h[i][1]++;
h[i][0]++;
v[h[i][0]].push_back(make_pair(h[i][1] , l[i]));
v[h[i][1]].push_back(make_pair(h[i][0] , l[i]));
}
precalc (1 , 0);
sol = 2000000000;
dfs (1 , 0 , k);
return (sol == 2000000000 ? -1 : sol);
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void precalc(int, int)':
race.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp:28:32: warning: 'fiu' may be used uninitialized in this function [-Wmaybe-uninitialized]
int i , vecin , maxi = 0 , fiu ;
^~~
# | 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... |