oj.uz

Submission #472494

# Submission time Handle Problem Language Result Execution time Memory
472494 2021-09-13T16:21:59 Z ZaZo_ Toll (BOI17_toll) C++14
18 / 100
 3000 ms 4572 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]=INT_MAX;
}
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] != INT_MAX) 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]!=INT_MAX)
        ans[v[i].first] = dist[v[i].second.second];
    }
  }
  for(int i = 0 ; i < o ; i++)
  cout<<ans[i]<<'\n';
}

Compilation message

toll.cpp: In function 'void djk(int, int)':
toll.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, std::pair<int, 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 3074 ms 3468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3604 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 1384 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 5 ms 1804 KB Output is correct
8 Correct 5 ms 1804 KB Output is correct
9 Correct 27 ms 3460 KB Output is correct
10 Correct 81 ms 4572 KB Output is correct
11 Correct 45 ms 3588 KB Output is correct
12 Correct 32 ms 3360 KB Output is correct
13 Correct 65 ms 4420 KB Output is correct
14 Correct 41 ms 3332 KB Output is correct
15 Correct 34 ms 3012 KB Output is correct
16 Correct 34 ms 2996 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 16 ms 1592 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 29 ms 3148 KB Output is correct
11 Correct 305 ms 3260 KB Output is correct
12 Correct 419 ms 4144 KB Output is correct
13 Correct 472 ms 4408 KB Output is correct
14 Correct 400 ms 3748 KB Output is correct
15 Correct 266 ms 2824 KB Output is correct
16 Correct 246 ms 2900 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 16 ms 1592 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 29 ms 3148 KB Output is correct
11 Correct 305 ms 3260 KB Output is correct
12 Correct 419 ms 4144 KB Output is correct
13 Correct 472 ms 4408 KB Output is correct
14 Correct 400 ms 3748 KB Output is correct
15 Correct 266 ms 2824 KB Output is correct
16 Correct 246 ms 2900 KB Output is correct
17 Execution timed out 3094 ms 3208 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 3074 ms 3468 KB Time limit exceeded
2 Halted 0 ms 0 KB -