oj.uz

Submission #472491

# Submission time Handle Problem Language Result Execution time Memory
472491 2021-09-13T16:15:03 Z ZaZo_ Toll (BOI17_toll) C++14
18 / 100
 3000 ms 8984 KB 
#include <bits/stdc++.h>
#define ZAZO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
vector<pair<int,int>>edges[50001];
int k , n , m , o ;
int dist[50001];
void prepare()
{
  for(int i = 0 ; i < n+1 ; i ++) dist[i]=1e15;
}
void djk(int s , int e)
{
  priority_queue<pair<int,int>>pq;
  dist[s]=0;
  pq.push({0,s});
  while(!pq.empty())
  {
    int c = -pq.top().first , u = pq.top().second;
    pq.pop();
    for(int i = 0 ; i < edges[u].size() ; i++)
    {
      if(dist[edges[u][i].first] > dist[u] + edges[u][i].second)
      {
        dist[edges[u][i].first] = dist[u] + edges[u][i].second;
        pq.push({-dist[edges[u][i].first],edges[u][i].first});
      }
    }
  }
}
int32_t main() {
  ZAZO
  cin >> k >> n >> m >> o ;
  for(int i = 0 ; i < m ; i ++)
  {
    int a , b , t;
    cin >> a >> b >> t;
    edges[a].push_back({b,t});
  }
  vector<pair<int,pair<int,int>>>v;
  for(int i = 0 ; i < o ; i ++)
  {
    int a , b;
    cin >> a >> b;
    v.push_back({i,{min(a,b),max(a,b)}});
  }
  sort(v.begin(),v.end());
  int ans[o];
  for(int i = 0 ; i < o ; i ++) ans[i]=-1;
  for(int i = 0 ; i < v.size() ; i++)
  {
    if(i && v[i].second.first == v[i-1].second.first)
    {
      if(dist[v[i].second.second] != 1e15) ans[v[i].first]=dist[v[i].second.second];
    }
    else
    {
      prepare();
      djk(v[i].second.first , v[i].second.second);
      if(dist[v[i].second.second]!=1e15)
        ans[v[i].first] = dist[v[i].second.second];
    }
  }
  for(int i = 0 ; i < o ; i++)
  cout<<ans[i]<<endl;
}

Compilation message

toll.cpp: In function 'void djk(long long int, long long int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0 ; i < edges[u].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
toll.cpp:19:9: warning: unused variable 'c' [-Wunused-variable]
   19 |     int c = -pq.top().first , u = pq.top().second;
      |         ^
toll.cpp: In function 'int32_t main()':
toll.cpp:50:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0 ; i < v.size() ; i++)
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 3784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4892 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 19 ms 2068 KB Output is correct
8 Correct 25 ms 2108 KB Output is correct
9 Correct 38 ms 4680 KB Output is correct
10 Correct 82 ms 8476 KB Output is correct
11 Correct 64 ms 6588 KB Output is correct
12 Correct 53 ms 5660 KB Output is correct
13 Correct 78 ms 8984 KB Output is correct
14 Correct 47 ms 5956 KB Output is correct
15 Correct 39 ms 5088 KB Output is correct
16 Correct 42 ms 5008 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 6 ms 1484 KB Output is correct
8 Correct 14 ms 1732 KB Output is correct
9 Correct 10 ms 1612 KB Output is correct
10 Correct 29 ms 4156 KB Output is correct
11 Correct 311 ms 5908 KB Output is correct
12 Correct 420 ms 8004 KB Output is correct
13 Correct 476 ms 8684 KB Output is correct
14 Correct 380 ms 6852 KB Output is correct
15 Correct 260 ms 4908 KB Output is correct
16 Correct 243 ms 4896 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 6 ms 1484 KB Output is correct
8 Correct 14 ms 1732 KB Output is correct
9 Correct 10 ms 1612 KB Output is correct
10 Correct 29 ms 4156 KB Output is correct
11 Correct 311 ms 5908 KB Output is correct
12 Correct 420 ms 8004 KB Output is correct
13 Correct 476 ms 8684 KB Output is correct
14 Correct 380 ms 6852 KB Output is correct
15 Correct 260 ms 4908 KB Output is correct
16 Correct 243 ms 4896 KB Output is correct
17 Execution timed out 3055 ms 6160 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 3784 KB Time limit exceeded
2 Halted 0 ms 0 KB -