이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#define DIM 100005
#define INF 1000000000000000LL
#define f first
#define s second
using namespace std;
int n, k, i, q, x, y, ii, c, rad, nod;
int niv[DIM], a[18][DIM], sh[DIM], b[DIM];
long long d[DIM], d2[18][DIM], sum[18][DIM], sol, tot;
pair<int, int> w[DIM];
vector< pair<int, int> > v[DIM];
void dfs(int nod, int t){
d[nod] = INF;
if(sh[nod] == 1){
d[nod] = 0;
}
for(int i = 0; i < v[nod].size(); i++){
int vecin = v[nod][i].f;
if(vecin != t){
a[0][vecin] = nod;
sum[0][vecin] = v[nod][i].s;
niv[vecin] = 1 + niv[nod];
dfs(vecin, nod);
d[nod] = min(d[nod], d[vecin] + v[nod][i].s);
}
}
}
int main(){
cin>> n >> k >> q >> rad;
for(i = 1; i < n; i++){
cin>> x >> y >> c;
w[i] = make_pair(x, y);
v[x].push_back( make_pair(y, c) );
v[y].push_back( make_pair(x, c) );
}
for(i = 1; i <= k; i++){
cin>> x;
sh[x] = 1;
}
dfs(rad, 0);
for(i = 1; i <= n; i++){
d2[0][i] = sum[0][i] + d[ a[0][i] ];
}
for(ii = 1; (1 << ii) < n; ii++){
for(i = 1; i <= n; i++){
a[ii][i] = a[ii - 1][ a[ii - 1][i] ];
if(a[ii][i] != 0){
sum[ii][i] = sum[ii - 1][i] + sum[ii - 1][ a[ii - 1][i] ];
d2[ii][i] = min(d2[ii - 1][i], sum[ii - 1][i] + d2[ii - 1][ a[ii - 1][i] ]);
}
}
}
for(i = 2; i <= n; i++){
b[i] = 1 + b[i / 2];
}
for(; q; q--){
cin>> ii >> x;
if(niv[ w[ii].f ] > niv[ w[ii].s ]){
y = w[ii].f;
}
else{
y = w[ii].s;
}
ii = niv[x] - niv[y];
nod = x;
while(ii > 0){
nod = a[ b[ii] ][nod];
ii -= (1 << b[ii]);
}
if(nod != y){
cout<<"escaped\n";
continue;
}
sol = d[x];
nod = x;
tot = 0;
ii = niv[x] - niv[y];
while(ii != 0){
sol = min(sol, tot + d2[ b[ii] ][nod]);
tot += sum[ b[ii] ][nod];
nod = a[ii][nod];
ii -= (1 << b[ii]);
}
if(sol >= INF){
cout<<"oo\n";
}
else{
cout<< sol <<"\n";
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < v[nod].size(); i++){
| ~~^~~~~~~~~~~~~~~
# | 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... |