이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define z return 0;
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 1; //
int p[N];
int get(int pos){
return p[pos] = p[pos] == pos ? pos : get(p[pos]);
}
void merge(int a, int b){
a = get(a), b = get(b);
p[a] = b;
}
void init(){
for (int i = 0; i < N; i++) p[i] = i;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n, m, k, t;
cin >> n >> m;
vector<pair<int, int>> g[n + 1], ord;
for (int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
cin >> k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int dis[n + 1];
for (int &i : dis) i = inf;
for (int i = 0, u; i < k; i++){
cin >> u;
q.push({0, u});
}
while (!q.empty()){
auto u = q.top();
q.pop();
if (u.fi >= dis[u.se]) continue;
ord.push_back({u.se, u.fi});
dis[u.se] = u.fi;
for (auto i : g[u.se]) q.push({u.fi + i.se, i.fi});
}
reverse(ord.begin(), ord.end());
cin >> t;
int l[t], r[t], st[t], ed[t];
for (int i = 0; i < t; i++){
cin >> st[i] >> ed[i];
l[i] = 0, r[i] = inf;
}
for (int _ = 0; _ < 31; _++){
init();
vector<pair<int, int>> vv;
for (int i = 0; i < t; i++){
int mid = l[i] + r[i] >> 1;
vv.push_back({mid, i});
}
sort(vv.begin(), vv.end(), greater<pair<int, int>>());
int vis[n + 1]{}, ptr = 0;
for (auto u : ord){
while (ptr < t and vv[ptr].fi > u.se){
int i = vv[ptr].se;
if (get(st[i]) == get(ed[i])) l[i] = (l[i] + r[i] >> 1) + 1;
else r[i] = l[i] + r[i] >> 1;
ptr++;
}
for (auto i : g[u.fi]) if (vis[i.fi]) merge(i.fi, u.fi);
vis[u.fi] = true;
}
}
for (int i = 0; i < t; i++) cout << max(0, l[i] - 1) << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int main()':
plan.cpp:57:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l[i] + r[i] >> 1;
| ~~~~~^~~~~~
plan.cpp:65:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | if (get(st[i]) == get(ed[i])) l[i] = (l[i] + r[i] >> 1) + 1;
| ~~~~~^~~~~~
plan.cpp:66:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | else r[i] = l[i] + r[i] >> 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |