# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
347768 | Dymo | Evacuation plan (IZhO18_plan) | C++14 | 1522 ms | 60140 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;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define eb emplace_back
#define ll long long
//#define ull unsigned long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e5+54;
const ll mod =2520 ;
const ll base=1e18;
ll dp[maxn];
vector<pll> adj[maxn];
priority_queue<pll,vector<pll>,greater<pll>> q;
void dosth()
{
while (!q.empty())
{
auto p=q.top();
q.pop();
if (dp[p.ss]!=p.ff) continue;
ll u=p.ss;
for (auto to:adj[u])
{
if (dp[to.ff]>dp[u]+to.ss)
{
dp[to.ff]=dp[u]+to.ss;
q.push(make_pair(dp[to.ff],to.ff));
}
}
}
}
pll a[maxn];
ll l[maxn];
ll r[maxn];
bool dd[maxn];
ll par[maxn];
ll find_par(ll u)
{
if (u==par[u]) return u;
return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
if (x==y) return ;
par[x]=y;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, m;
cin>>n >> m;
for (int i=1;i<=m;i++)
{
ll x, y, w;
cin>> x>> y>> w;
adj[x].pb(make_pair(y,w));
adj[y].pb(make_pair(x,w));
}
for (int i=1;i<=n;i++)
{
dp[i]=1e15;
}
ll k;
cin>> k;
for (int i=1;i<=k;i++)
{
ll x;
cin>> x;
dp[x]=0;
q.push(make_pair(dp[x],x));
}
dosth();
ll q;
cin>> q;
for (int i=1;i<=q;i++)
{
cin>>a[i].ff>>a[i].ss;
}
vector<pll> b;
ll mx=0;
for (int i=1;i<=n;i++)
{
mx=max(mx,dp[i]);
b.pb(make_pair(dp[i],i));
}
sort(b.rbegin(),b.rend());
for (int i=1;i<=q;i++)
{
l[i]=0;
r[i]=mx;
}
while (1)
{
for (int i=1;i<=n;i++) dd[i]=0, par[i]=i ;
vector<pair<ll,ll>> gr;
for (int i=1;i<=q;i++)
{
if (l[i]<=r[i])
{
gr.pb(make_pair((l[i]+r[i])/2,i));
}
}
if (gr.size())
{
sort(gr.rbegin(),gr.rend());
}
else break;
ll idnw=0;
for (auto p:gr)
{
ll val=p.ff;
while (idnw<b.size()&&val<=b[idnw].ff)
{
dd[b[idnw].ss]=1;
ll u=b[idnw].ss;
for (auto to:adj[u])
{
if (dd[to.ff])
{
dsu(to.ff,u);
}
}
idnw++;
}
ll x=a[p.ss].ff;
ll y=a[p.ss].ss;
if (find_par(x)==find_par(y))
{
l[p.ss]=val+1;
}
else
{
r[p.ss]=val-1;
}
}
}
for (int i=1;i<=q;i++)
{
cout <<r[i]<<endl;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5*/
}
Compilation message (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... |