# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
96904 | Kalam | Evacuation plan (IZhO18_plan) | C++11 | 1095 ms | 67048 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// KALAM
# include<bits/stdc++.h>
using namespace std;
const int N = 500000 + 77;
int n , m , q , k , d[N] , Ev[N] , Eu[N] , Ew[N] , Qv[N] , Qu[N] , P[N] , A[N] , Par[N];
bool M[N];
vector < int > a[N];
set < int > S[N];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Pq;
bool CMP(int x , int y){
return Ew[x] > Ew[y];
}
int Find(int x){
return Par[x] < 0 ? x : (Par[x] = Find(Par[x]));
}
inline void Merge(int v , int u , int w){
v = Find(v);
u = Find(u);
if(v == u)
return ;
if(Par[v] > Par[u])
swap(v , u);
Par[v] += Par[u];
Par[u] = v;
for(int x : S[u]){
auto it = S[v].lower_bound(x);
if(it != S[v].end() && (*it) == x)
A[x] = w , S[v].erase(it);
else
S[v].insert(x);
}
S[u].clear();
}
int main(){
memset(Par , - 1 , sizeof(Par));
memset(d , 63 , sizeof(d));
scanf("%d %d" , & n , & m);
for(int i = 1;i <= m;++ i) {
scanf("%d %d %d" , Ev + i , Eu + i , Ew + i);
a[Ev[i]].push_back(i);
a[Eu[i]].push_back(i);
}
scanf("%d" , & k);
while(k --){
int x;
scanf("%d" , & x);
d[x] = 0;
Pq.push(make_pair(d[x] , x));
}
while(! Pq.empty()){
int v = Pq.top().second;
Pq.pop();
if(M[v])
continue ;
M[v] = 1;
for(int id : a[v]){
int u = Ev[id] ^ v ^ Eu[id] , w = Ew[id];
if(d[u] <= d[v] + w)
continue ;
d[u] = d[v] + w;
Pq.push(make_pair(d[u] , u));
}
}
for(int i = 1;i <= m;++ i)
P[i] = i , Ew[i] = min(d[Ev[i]] , d[Eu[i]]);
sort(P + 1 , P + 1 + m , CMP);
scanf("%d" , & q);
for(int i = 1;i <= q;++ i){
scanf("%d %d" , Qv + i , Qu + i);
S[Qv[i]].insert(i);
S[Qu[i]].insert(i);
}
for(int i = 1;i <= m;++ i){
int id = P[i];
Merge(Ev[id] , Eu[id] , Ew[id]);
}
for(int i = 1;i <= q;++ i)
printf("%d\n" , A[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |