oj.uz

Submission #472495

# Submission time Handle Problem Language Result Execution time Memory
472495 2021-09-13T16:22:37 Z ZaZo_ Toll (BOI17_toll) C++14
18 / 100
 3000 ms 4448 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,{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 3086 ms 3476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3460 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 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 5 ms 1804 KB Output is correct
8 Correct 6 ms 1804 KB Output is correct
9 Correct 23 ms 3472 KB Output is correct
10 Correct 72 ms 4448 KB Output is correct
11 Correct 46 ms 3540 KB Output is correct
12 Correct 34 ms 3368 KB Output is correct
13 Correct 66 ms 4392 KB Output is correct
14 Correct 41 ms 3268 KB Output is correct
15 Correct 33 ms 2984 KB Output is correct
16 Correct 33 ms 2988 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 1408 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 14 ms 1588 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 27 ms 3192 KB Output is correct
11 Correct 281 ms 3328 KB Output is correct
12 Correct 404 ms 4140 KB Output is correct
13 Correct 476 ms 4412 KB Output is correct
14 Correct 369 ms 3740 KB Output is correct
15 Correct 252 ms 2868 KB Output is correct
16 Correct 250 ms 3012 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 1408 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 14 ms 1588 KB Output is correct
9 Correct 10 ms 1484 KB Output is correct
10 Correct 27 ms 3192 KB Output is correct
11 Correct 281 ms 3328 KB Output is correct
12 Correct 404 ms 4140 KB Output is correct
13 Correct 476 ms 4412 KB Output is correct
14 Correct 369 ms 3740 KB Output is correct
15 Correct 252 ms 2868 KB Output is correct
16 Correct 250 ms 3012 KB Output is correct
17 Execution timed out 3058 ms 3304 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 3086 ms 3476 KB Time limit exceeded
2 Halted 0 ms 0 KB -