oj.uz

Submission #889216

# Submission time Handle Problem Language Result Execution time Memory
889216 2023-12-19T08:03:17 Z hariaakas646 Olympic Bus (JOI20_ho_t4) C++17
16 / 100
 55 ms 4180 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

struct Edge {
    int u, v, c, d;
};

int main() {
    // usaco();
    int n, m;
    scd(n);
    scd(m);

    vector<Edge> vec(m);

    vector<seti> graph(n+1);

    vector<vll> dist(n+1, vll(n+1, 1e17));

    forr(i, 1, n+1) dist[i][i] = 0;

    frange(i, m) {
        int u, v, c, d;
        scd(u);
        scd(v);
        scd(c);
        scd(d);
        vec[i].u = u;
        vec[i].v = v;
        vec[i].c = c;
        vec[i].d = d;

        dist[u][v] = min(dist[u][v], (lli)c);
        graph[u].insert(i);
    }

    forr(k, 1, n+1) {
        forr(i, 1, n+1) {
            forr(j, 1, n+1) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vb inpath(m);

    queue<pii> q;
    q.push(mp(1, -10));
    vi par(n+1, -1);
    if(dist[1][n] < 1e16)
    {
        while(q.size()) {
            auto p = q.front();
            q.pop();
            if(par[p.f] != -1) continue;
            par[p.f] = p.s;

            if(p.f == n) {
                int curr = n;
                while(curr != 1) {
                    // printf("%d ", curr);
                    inpath[par[curr]] = true;
                    curr = vec[par[curr]].u;
                }
            }

            for(auto e : graph[p.f]) {
                if(dist[1][vec[e].u] + vec[e].c + dist[vec[e].v][n] == dist[1][n]) {
                    q.push(mp(vec[e].v, e));
                }
            }
        }
        
    }

    lli mi = dist[1][n] + dist[n][1];

    // frange(i, m) {
    //     auto p = vec[i];
    //     lli v = dist[n][p.v] + dist[p.u][1] + p.c + p.d;

    //     if(v + dist[1][n] < mi) {
    //         graph[p.u].erase(i);
    //         graph[p.v].insert(i);

    //         swap(vec[i].u, vec[i].v);
    
    //         vll dist2(n+1, 1e16);
    //         priority_queue<pair<lli, int>> pq;
    //         pq.push(mp(0, 1));
    //         dist2[1] = 0;
    //         vb vis(n+1);
    //         while(pq.size()) {
    //             auto p = pq.top();
    //             pq.pop();
    
    //             if(vis[p.s]) continue;
    //             vis[p.s] = true;
    
    //             for(auto j : graph[p.s]) {
    //                 auto e = vec[j];
    //                 if(dist2[p.s] + e.c < dist2[e.v]) {
    //                     dist2[e.v] = dist2[p.s] + e.c;
    //                     pq.push(mp(-dist2[e.v], e.v));
    //                 }
    //             }
    //         }
    //         v += dist2[n];
    //         graph[p.v].erase(i);
    //         graph[p.u].insert(i);
    //         mi = min(mi, v);
    //         swap(vec[i].u, vec[i].v);
    //     }
    //     // else {
    //     //     v += dist[1][n];
    //     // }
    //     // mi = min(mi, v);
    // }

    vb inpath2(m);

    q = {};
    q.push(mp(n, -10));
    par = vi(n+1, -1);
    if(dist[n][1] < 1e16)
    {
        while(q.size()) {
            auto p = q.front();
            q.pop();
            if(par[p.f] != -1) continue;
            par[p.f] = p.s;

            if(p.f == 1) {
                int curr = 1;
                while(curr != n) {
                    // printf("%d ", curr);
                    inpath2[par[curr]] = true;
                    curr = vec[par[curr]].u;
                }
            }

            for(auto e : graph[p.f]) {
                if(dist[n][vec[e].u] + vec[e].c + dist[vec[e].v][1] == dist[n][1]) {
                    q.push(mp(vec[e].v, e));
                }
            }
        }
        
    }

    frange(i, m) {
        auto p = vec[i];
        // lli v = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c) + p.d;

        lli d1 = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c);
        lli d2 = min(dist[n][1], dist[n][p.v] + dist[p.u][1] + p.c);

        lli v = p.d;
        if(dist[1][n] < dist[1][p.v] + dist[p.u][n] + p.c && inpath[i]) {
            graph[p.u].erase(i);
            graph[p.v].insert(i);

            swap(vec[i].u, vec[i].v);
    
            vll dist2(n+1, 1e16);
            priority_queue<pair<lli, int>> pq;
            pq.push(mp(0, 1));
            dist2[1] = 0;
            vb vis(n+1);
            while(pq.size()) {
                auto p = pq.top();
                pq.pop();
    
                if(vis[p.s]) continue;
                vis[p.s] = true;
    
                for(auto j : graph[p.s]) {
                    auto e = vec[j];
                    if(dist2[p.s] + e.c < dist2[e.v]) {
                        dist2[e.v] = dist2[p.s] + e.c;
                        pq.push(mp(-dist2[e.v], e.v));
                    }
                }
            }
            v += dist2[n];

            graph[p.v].erase(i);
            graph[p.u].insert(i);

            swap(vec[i].u, vec[i].v);
        }
        else v += min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c);

        if(dist[n][1] < dist[n][p.v] + dist[p.u][1] + p.c && inpath2[i]) {
            graph[p.u].erase(i);
            graph[p.v].insert(i);

            swap(vec[i].u, vec[i].v);
    
            vll dist2(n+1, 1e16);
            priority_queue<pair<lli, int>> pq;
            pq.push(mp(0, n));
            dist2[n] = 0;
            vb vis(n+1);
            while(pq.size()) {
                auto p = pq.top();
                pq.pop();
    
                if(vis[p.s]) continue;
                vis[p.s] = true;
    
                for(auto j : graph[p.s]) {
                    auto e = vec[j];
                    if(dist2[p.s] + e.c < dist2[e.v]) {
                        dist2[e.v] = dist2[p.s] + e.c;
                        pq.push(mp(-dist2[e.v], e.v));
                    }
                }
            }
            v += dist2[1];

            graph[p.v].erase(i);
            graph[p.u].insert(i);
            swap(vec[i].u, vec[i].v);
        }
        else v += min(dist[n][1], dist[n][p.v] + dist[p.u][1] + p.c);

        
        // else {
        //     v += dist[n][1];
        // }
        mi = min(mi, v);
    }

    // frange(i, m) {
    //     auto p = vec[i];
    //     lli v = dist[1][p.v] + dist[p.u][n] + p.c + p.d + dist[n][p.v] + dist[p.u][1] + p.c;
    //     mi = min(mi, v);
    // }

    if(mi < 1e16) printf("%lld", mi);
    else printf("-1");

}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:185:13: warning: unused variable 'd1' [-Wunused-variable]
  185 |         lli d1 = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c);
      |             ^~
ho_t4.cpp:186:13: warning: unused variable 'd2' [-Wunused-variable]
  186 |         lli d2 = min(dist[n][1], dist[n][p.v] + dist[p.u][1] + p.c);
      |             ^~
ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:41:5: note: in expansion of macro 'scd'
   41 |     scd(n);
      |     ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:42:5: note: in expansion of macro 'scd'
   42 |     scd(m);
      |     ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:54:9: note: in expansion of macro 'scd'
   54 |         scd(u);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:55:9: note: in expansion of macro 'scd'
   55 |         scd(v);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:56:9: note: in expansion of macro 'scd'
   56 |         scd(c);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:57:9: note: in expansion of macro 'scd'
   57 |         scd(d);
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 7 ms 856 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 7 ms 776 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 23 ms 604 KB Output is correct
11 Correct 23 ms 844 KB Output is correct
12 Correct 24 ms 836 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 8 ms 844 KB Output is correct
15 Correct 7 ms 844 KB Output is correct
16 Correct 7 ms 860 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3924 KB Output is correct
2 Correct 35 ms 3888 KB Output is correct
3 Correct 44 ms 3920 KB Output is correct
4 Correct 11 ms 856 KB Output is correct
5 Correct 10 ms 600 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 34 ms 3676 KB Output is correct
10 Correct 39 ms 3676 KB Output is correct
11 Correct 37 ms 3844 KB Output is correct
12 Correct 36 ms 3912 KB Output is correct
13 Correct 46 ms 3880 KB Output is correct
14 Correct 55 ms 3804 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 7 ms 784 KB Output is correct
3 Correct 34 ms 3720 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 37 ms 4180 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 7 ms 856 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 7 ms 776 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 23 ms 604 KB Output is correct
11 Correct 23 ms 844 KB Output is correct
12 Correct 24 ms 836 KB Output is correct
13 Correct 7 ms 860 KB Output is correct
14 Correct 8 ms 844 KB Output is correct
15 Correct 7 ms 844 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 36 ms 3924 KB Output is correct
18 Correct 35 ms 3888 KB Output is correct
19 Correct 44 ms 3920 KB Output is correct
20 Correct 11 ms 856 KB Output is correct
21 Correct 10 ms 600 KB Output is correct
22 Correct 10 ms 604 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 34 ms 3676 KB Output is correct
26 Correct 39 ms 3676 KB Output is correct
27 Correct 37 ms 3844 KB Output is correct
28 Correct 36 ms 3912 KB Output is correct
29 Correct 46 ms 3880 KB Output is correct
30 Correct 55 ms 3804 KB Output is correct
31 Correct 7 ms 604 KB Output is correct
32 Correct 7 ms 784 KB Output is correct
33 Correct 34 ms 3720 KB Output is correct
34 Correct 9 ms 604 KB Output is correct
35 Correct 37 ms 4180 KB Output is correct
36 Incorrect 1 ms 348 KB Output isn't correct
37 Halted 0 ms 0 KB -