| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 334797 | beksultan04 | Evacuation plan (IZhO18_plan) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define endi puts("");
const int N = 1e5+12,INF=1e9+7;
int dist[N],n,yy,ans,batya[N],;
vector <pii> g[N];
bool is[N];
set <pii> s;
void fun(){
int i,j,k;
while (!s.empty()){
pii x = *s.begin();
s.erase(s.begin());
for (i=0;i<g[x.sc].size();++i){
if (dist[g[x.sc][i].fr] > dist[x.sc]+g[x.sc][i].sc){
s.erase({dist[g[x.sc][i].fr],g[x.sc][i].fr});
dist[g[x.sc][i].fr] = dist[x.sc]+g[x.sc][i].sc;
s.insert({dist[g[x.sc][i].fr],g[x.sc][i].fr});
}
}
}
}
int find_baty(int a){
if (a == batya[a])ret a;
ret batya[a] = find_baty(batya[a]);
}
void unite(int a,int b){
batya[a] = b;
}
main(){
int m,i,j;
scan2(n,m)
for (i=1;i<=n;++i)dist[i]=INF;
while (m--){
int x,y,z;
scan3(x,y,z)
g[x].pb({y,z});
g[y].pb({x,z});
}
scan1(m)
while (m--){
int x;
scan1(x)
dist[x] = 0;
s.insert({0,x});
}
fun();
for(i = 1; i <= n; i++){
v.pb({dis[i],i});
}
sort(all(v));
reverse(all(v));
scan1(m)
for (i=1;i<=m;++i){
int x,y;
scan2(x,y)
s[x].insert(i);
s[y].insert(i);
p[i]={x,y};
}
for (i=0;i<v.size();++i){
int x = v[i];
for (j=0;j<g[x].size();++j){
int to = g[x][j];
if (is[to]){
unite(x,find_baty(to));
}
}
}
}