oj.uz

Submission #1114826

# Submission time Handle Problem Language Result Execution time Memory
1114826 2024-11-19T16:35:19 Z AdamGS Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 262144 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

struct Edge{
    int other, len, swapCost;
    bool active=true;
};

vector<vector<Edge>> graph;
vector<bool> found;

int Dijkstra(int v1, int v2){
    for (int i=0;i<found.size();i++) found[i]=false;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, v1});
    while (!pq.empty()){
        pair<int, int> p=pq.top();
        pq.pop();
        if (p.second==v2) return p.first;
        found[p.second]=true;
        for (Edge e:graph[p.second]){
            if (e.active&&!found[e.other]) pq.push({p.first+e.len, e.other});
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    graph.resize(n+7);
    found.resize(n+7);
    for (int i=0;i<m;i++){
        Edge e;
        int v;
        cin>>v>>e.other>>e.len>>e.swapCost;
        graph[v].push_back(e);
    }
    int d1=Dijkstra(1, n), d2=Dijkstra(n, 1), out;
    if (d1==-1||d2==-1) out=-1;
    else out=d1+d2;
    for (int i=1;i<=n;i++){
        for (int j=0;j<graph[i].size();j++){
            graph[i][j].active=false;
            Edge e;
            e.len=graph[i][j].len;
            e.other=i;
            graph[graph[i][j].other].push_back(e);
            int dist1=Dijkstra(1, n), dist2=Dijkstra(n, 1), res;
            graph[graph[i][j].other].pop_back();
            graph[i][j].active=true;
            if (dist1==-1||dist2==-1) res=-1;
            else res=dist1+dist2+graph[i][j].swapCost;
            if (out==-1) out=res;
            else  if (res!=-1) out=min(out, res);
        }
    }
    cout<<out<<'\n';
    return 0;
}

Compilation message

ho_t4.cpp: In function 'int Dijkstra(int, int)':
ho_t4.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0;i<found.size();i++) found[i]=false;
      |                  ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j=0;j<graph[i].size();j++){
      |                      ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 20 ms 528 KB Output is correct
4 Correct 42 ms 336 KB Output is correct
5 Correct 24 ms 504 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 11 ms 336 KB Output is correct
10 Correct 80 ms 584 KB Output is correct
11 Correct 70 ms 336 KB Output is correct
12 Correct 78 ms 336 KB Output is correct
13 Correct 35 ms 336 KB Output is correct
14 Correct 47 ms 336 KB Output is correct
15 Correct 40 ms 520 KB Output is correct
16 Correct 94 ms 336 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 336 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Runtime error 448 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 20 ms 528 KB Output is correct
4 Correct 42 ms 336 KB Output is correct
5 Correct 24 ms 504 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 11 ms 336 KB Output is correct
10 Correct 80 ms 584 KB Output is correct
11 Correct 70 ms 336 KB Output is correct
12 Correct 78 ms 336 KB Output is correct
13 Correct 35 ms 336 KB Output is correct
14 Correct 47 ms 336 KB Output is correct
15 Correct 40 ms 520 KB Output is correct
16 Correct 94 ms 336 KB Output is correct
17 Execution timed out 1066 ms 30632 KB Time limit exceeded
18 Halted 0 ms 0 KB -