oj.uz

Submission #565679

# Submission time Handle Problem Language Result Execution time Memory
565679 2022-05-21T09:10:52 Z Dodo Evacuation plan (IZhO18_plan) C++14
22 / 100
 4000 ms 43840 KB 
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pb push_back
using namespace std;
const ll mx=100006;
ll INF = 100000000000000008;
ll n,m;
vector<pair<ll,ll>>v[mx];
ll d[mx];

void dij(ll x)
{
  ll dis[n+1];
  for(int i=1;i<=n;i++)dis[i]=INF;

  bool st[n+1]={};
  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>> > pq;

  dis[x]=0;
  ll cnt=1;
  st[x]=1;

  for(auto u:v[x])
  {
    pq.push({u.second,u.first});
    dis[u.first]=u.second;
  }

  while(cnt!=n)
  {
    while(st[pq.top().second])pq.pop();
    cnt++;
    ll ve=pq.top().second;
    st[ve]=1;
    for(auto u:v[ve])
    {
      if(st[u.first])continue;
      dis[u.first]=min(dis[u.first],dis[ve]+u.second);
      pq.push({dis[u.first],u.first});
    }
  }

  for(int i=1;i<=n;i++)d[i]=min(d[i],dis[i]);
}


ll solve(ll a,ll b)
{
  if(d[a]==0||d[b]==0)return 0;
  ll mn=d[a];
  bool st[n+1]={};
  priority_queue<pair<ll,ll>> pq;
  st[a]=1;

  for(auto u:v[a])
    pq.push({d[u.first],u.first});

  while(st[b]==0)
  {
    while(st[pq.top().second])pq.pop();
    ll ve=pq.top().second;
    st[ve]=1;
    mn=min(mn,d[ve]);

    for(auto u:v[ve])
    {
      if(st[u.first])continue;
      pq.push({d[u.first],u.first});
    }
  }
  return mn;
}


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin>>n>>m;
  for(int i=1;i<=n;i++)d[i]=INF;
  while(m--)
  {
    ll a,b,w;
    cin>>a>>b>>w;
    v[a].push_back({b,w});
    v[b].push_back({a,w});
  }


  ll k;
  cin>>k;
  for(int i=0;i<k;i++)
  {
    ll x;
    cin>>x;
    dij(x);
  }

  ll q;
  cin>>q;
  while(q--)
  {
    ll a,b;
    cin>>a>>b;
    cout<<solve(a,b)<<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
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 37 ms 2772 KB Output is correct
3 Correct 38 ms 2756 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 41 ms 2772 KB Output is correct
6 Correct 67 ms 2752 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 4 ms 2644 KB Output is correct
10 Correct 61 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 39 ms 2780 KB Output is correct
13 Correct 11 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 37 ms 2772 KB Output is correct
3 Correct 38 ms 2756 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 41 ms 2772 KB Output is correct
6 Correct 67 ms 2752 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 4 ms 2644 KB Output is correct
10 Correct 61 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 39 ms 2780 KB Output is correct
13 Correct 11 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Execution timed out 4074 ms 10192 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2680 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 18336 KB Output is correct
2 Correct 460 ms 39512 KB Output is correct
3 Correct 680 ms 43608 KB Output is correct
4 Correct 109 ms 11052 KB Output is correct
5 Correct 1829 ms 43668 KB Output is correct
6 Execution timed out 4056 ms 43840 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 37 ms 2772 KB Output is correct
3 Correct 38 ms 2756 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 41 ms 2772 KB Output is correct
6 Correct 67 ms 2752 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 4 ms 2644 KB Output is correct
10 Correct 61 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 39 ms 2780 KB Output is correct
13 Correct 11 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Execution timed out 4074 ms 10192 KB Time limit exceeded
17 Halted 0 ms 0 KB -