oj.uz

Submission #713003

# Submission time Handle Problem Language Result Execution time Memory
713003 2023-03-20T19:11:25 Z thimote75 Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 2000 ms 155940 KB 
#include <bits/stdc++.h>

using namespace std;

#define num long long
#define t_road pair<int, num>
#define s second
#define cost s
#define f first
#define next f
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define ndata vector<num>
#define dn pair<num, int>

graph roads;
graph residual;
graph residual_r;

vector<dn> propagation;

void dij (int start, vector<num> &res) {
    fill(res.begin(), res.end(), 1e18);
    
    res[start] = 0;

    priority_queue<t_road> queue;
    queue.push({ 0, start });

    while (queue.size() != 0) {
        t_road r = queue.top();
        queue.pop();

        int curr = r.s;
        int val  = r.f;
        if (val != res[curr]) continue ;

        for (t_road road : roads[curr]) {
            if (res[road.next] <= res[curr] + road.cost) continue ;

            res[road.next] = res[curr] + road.cost;
            queue.push({ res[road.next], road.next });
        }
    }
}

vector<bool> visited;
void dfs (vector<num> &res, int node) {
    if (visited[node]) return ;
    visited[node] = true;
    propagation.push_back({ res[node], node });

    for (t_road road : roads[node]) {
        if (res[road.next] + road.cost != res[node]) continue ;
    
        residual[node].push_back(road);
        residual_r[road.next].push_back({ node, road.cost });
        
        dfs(res, road.next);
    }
}

void propagate (vector<num> &res, graph &r, int node) {
    for (t_road road : r[node])
        res[road.next] = min(res[road.next], res[node]);
}
void propagate (vector<num> &res, graph &r) {
    for (dn prop_node : propagation)
        propagate(res, r, prop_node.second);
}

void show (vector<num> &res, string s) {
    cout << "--- " << s << " ---" << endl;
    for (int i = 0; i < res.size(); i ++)
        printf("%lld ", res[i]);
    cout << endl;
}

int main () {
    int nbNodes, nbRoads;
    cin >> nbNodes >> nbRoads;

    int h, t, a, b;
    cin >> h >> t >> a >> b;
    h --; t --; a --; b --;

    roads.resize(nbNodes);
    residual.resize(nbNodes);
    residual_r.resize(nbNodes);
    visited.resize(nbNodes, false);

    for (int iR = 0; iR < nbRoads; iR ++) {
        int l, r, cst;
        cin >> l >> r >> cst;
        l --; r --;

        roads[l].push_back({ r, cst });
        roads[r].push_back({ l, cst });
    }

    ndata H(nbNodes), A(nbNodes), B(nbNodes), C(nbNodes);
    dij(h, H);
    dij(a, A);
    dij(b, B);

    dfs (H, t);
    //for (dn data : propagation)
    //    printf("%d ", data.second);
    //cout << endl;

    //show(A, "A0");
    //show(B, "B0");

    for (int id = 0; id < C.size(); id ++) C[id] = A[id];

    sort(propagation.rbegin(), propagation.rend());
    propagate(A, residual);
    reverse(propagation.begin(), propagation.end());
    propagate(C, residual_r);

    //show(H, "H");
    //show(A, "A1");
    //show(B, "B1");

    num answer = 1e18;
    for (int id = 0; id < nbNodes; id ++)
        answer = min(answer, min(C[id], A[id]) + B[id]);

    cout << answer << endl;
}

Compilation message

commuter_pass.cpp: In function 'void show(std::vector<long long int>&, std::string)':
commuter_pass.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < res.size(); i ++)
      |                     ~~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:115:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int id = 0; id < C.size(); id ++) C[id] = A[id];
      |                      ~~~^~~~~~~~~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2388 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 35 ms 3700 KB Output is correct
5 Correct 21 ms 2040 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 16 ms 724 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 30 ms 2004 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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