이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
int n, m;
const int MAXN = 1e5+1; //M <= 5e5+1 dock
vector<pair<int, int> > adj[MAXN];
int weight[MAXN];
vector<int> edgesMST[MAXN];
int binPar[MAXN][20];
int binWeight[MAXN][20];
bool isVisited[MAXN];
bool active[MAXN];
int depth[MAXN];
void initBin(){
for (int j = 1; j < 20; j++){
for (int i = 0; i < n; i++){
binPar[i][j] = binPar[binPar[i][j-1]][j-1];
binWeight[i][j] = min(binWeight[i][j-1], binWeight[binPar[i][j-1]][j-1]);
}
}
}
int jump(int x, int k){
for (int i = 19; i >= 0; i--){
if (k&(1<<i))x = binPar[x][i];
}
return x;
}
int lca(int a, int b){
if (depth[a] < depth[b])swap(a, b);
a = jump(a, depth[a]-depth[b]);
if (a == b)return a;
for (int i = 19; i >= 0; i--){
int aT = binPar[a][i], bT = binPar[b][i];
if (aT != bT){
a = aT;
b = bT;
}
}
return binPar[a][0];
}
int getMin(int node, int k){
int mini = weight[node];
for (int i = 19; i >= 0; i--){
if (k&(1<<i)){
mini = min(mini, binWeight[node][i]);
node = binPar[node][i];
//cout << "; " << i << " " << binWeight[node][i] << endl;
}
}
return mini;
}
int main(){
scoobydoobydoo();
cin >> n >> m;
for (int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w;
a--; b--;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
int k; cin >> k;
vector<int> NPP(k);
priority_queue<pair<int, int> > pq;
for (int i = 0; i < k; i++){
cin >> NPP[i];
pq.push({0, --NPP[i]});
}
int maxi = -1;
int best;
while (!pq.empty()){
int node = pq.top().second;
int w = -pq.top().first;
pq.pop();
if (isVisited[node])continue;
isVisited[node] = true;
weight[node] = w;
if (weight[node] > maxi){
maxi = w;
best = node;
}
for (auto p : adj[node]){
if (!isVisited[p.first])pq.push({-(w+p.second), p.first});
}
}
active[best] = true;
priority_queue<vector<int> > sPq;
for (auto p : adj[best]){
sPq.push({weight[best], p.first, best, 1});
}
depth[best] = 0;
binPar[best][0] = best;
while (!sPq.empty()){
int node = sPq.top()[1];
int w = sPq.top()[0];
int pare = sPq.top()[2];
int dpt = sPq.top()[3];
sPq.pop();
if (active[node])continue;
active[node] = true;
binPar[node][0] = pare;
binWeight[node][0] = w;
depth[node] = dpt;
for (auto p : adj[node]){
if (!active[p.first])sPq.push({weight[node], p.first, node, dpt+1});
}
}
initBin();
vector<int> ans;
int q; cin >> q;
while (q--){
int s, t; cin >> s >> t;
s--; t--;
int LC = lca(s, t);
//cout << s << " " << t << " " << LC << endl;
//cout << getMin(s, depth[s]-depth[LC]) << " " << getMin(t, depth[t]-depth[LC]) << endl;
ans.push_back(min(getMin(s, depth[s]-depth[LC]), getMin(t, depth[t]-depth[LC])));
}
for (int x : ans){
cout << x << endl;
}
/*for (int i = 0; i < n; i++)cout << i << ": " << depth[i] << ", ";
cout << endl;
for (int i = 0; i < n; i++){
cout << i << ": " << endl << binPar[i][0] << " " << binPar[i][1] << " " << binPar[i][2] << endl;
cout << binWeight[i][0] << " " << binWeight[i][1] << " " << binWeight[i][2] << endl;
}*/
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int main()':
plan.cpp:131:21: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | binPar[best][0] = best;
| ~~~~~~~~~~~~~~~~^~~~~~
# | 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... |