oj.uz

Submission #888882

# Submission time Handle Problem Language Result Execution time Memory
888882 2023-12-18T10:31:40 Z hariaakas646 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 61 ms 4692 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);

    int curr = 1;
    int k = 0;
    if(dist[1][n] < 1e16)
    {
        while(curr != n) {
            for(auto e : graph[curr]) {
                if(vec[e].c + dist[vec[e].v][n] == dist[vec[e].u][n]) {
                    curr = vec[e].v;
                    inpath[e] = true;
                    break;
                }
            }
            k++;
            if(k > 1000) break;
        }
        
    }

    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(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 += dist[1][n];
        }
        mi = min(mi, v);
    }

    inpath = vb(m);

    curr = n;
    k = 0;
    if(dist[n][1] < 1e16) 
    {
        while(curr != 1) {
            for(auto e : graph[curr]) {
                if(vec[e].c + dist[vec[e].v][1] == dist[vec[e].u][1]) {
                    curr = vec[e].v;
                    inpath[e] = true;
                    break;
                }
            }
            k++;
            if(k > 1000) break;
        }
        
    }

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

        if(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, 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 += dist[n][1];
        }
        mi = min(mi, v);
    }

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

}

Compilation message

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 7 ms 692 KB Output is correct
7 Correct 0 ms 428 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 21 ms 604 KB Output is correct
11 Correct 20 ms 844 KB Output is correct
12 Correct 20 ms 600 KB Output is correct
13 Incorrect 8 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3920 KB Output is correct
2 Correct 36 ms 3676 KB Output is correct
3 Correct 38 ms 3924 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 7 ms 824 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 30 ms 3888 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 7 ms 700 KB Output is correct
3 Correct 61 ms 3932 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 45 ms 4692 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 36 ms 4640 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 7 ms 692 KB Output is correct
7 Correct 0 ms 428 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 21 ms 604 KB Output is correct
11 Correct 20 ms 844 KB Output is correct
12 Correct 20 ms 600 KB Output is correct
13 Incorrect 8 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -