oj.uz

Submission #400164

# Submission time Handle Problem Language Result Execution time Memory
400164 2021-05-07T13:19:58 Z SavicS Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 31 ms 1820 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m;
array<int,4> niz[maxn];

bool used[maxn];

const int N = 205;
vector<int> g[N];
vector<int> rg[N];

int dist[2][N]; // 0 - 1, 1 - n
int from[2][N]; // 0 - 1, 1 - n
void dij1(int s, int dist[], int from[]){
    ff(i,1,n)dist[i] = inf;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({dist[s] = 0, s});
    while(!pq.empty()){
        pii v = pq.top(); pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(int c : g[v.se]){
            int u = niz[c][1];
            int w = niz[c][2];
            if(v.se != niz[c][0])continue;
            if(dist[u] > w + v.fi){
                pq.push({dist[u] = w + v.fi, u});
                from[u] = c;
            }
        }
    }

}

int rdist[2][N]; // 0 - 1, 1 - n
void dij2(int s, int dist[]){
    ff(i,1,n)dist[i] = inf;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({dist[s] = 0, s});
    while(!pq.empty()){
        pii v = pq.top(); pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(int c : rg[v.se]){
            int u = niz[c][0];
            int w = niz[c][2];
            if(dist[u] > w + v.fi){
                pq.push({dist[u] = w + v.fi, u});
            }
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> m;
    ff(i,1,m){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        g[u].pb(i);
        rg[v].pb(i);
        niz[i] = {u, v, c, d};
    }

    dij1(1, dist[0], from[0]), dij1(n, dist[1], from[1]);
    dij2(1, rdist[0]), dij2(n, rdist[1]);

    int cur = n;
    while(from[0][cur] && cur != 1){
        used[from[0][cur]] = 1;
        cur = niz[from[0][cur]][0];
    }

    cur = 1;
    while(from[1][cur] && cur != n){
        used[from[1][cur]] = 1;
        cur = niz[from[1][cur]][0];
    }

    int rez = dist[0][n] + dist[1][1];
    ff(i,1,m){
        int u = niz[i][0];
        int v = niz[i][1];
        int c = niz[i][2];
        int d = niz[i][3];
        if(!used[i]){

            int A = min(dist[0][n], dist[0][v] + c + rdist[1][u]);
            int B = min(dist[1][1], dist[1][v] + c + rdist[0][u]);

            rez = min(rez, A + B + d);

        }

    }

    ff(i,1,m){
        int u = niz[i][0];
        int v = niz[i][1];
        int c = niz[i][2];
        int d = niz[i][3];
        if(used[i]){
            swap(niz[i][0], niz[i][1]);
            g[v].pb(i);
            dij1(1, dist[0], from[0]), dij1(n, dist[1], from[1]);
            g[v].pop_back();
            swap(niz[i][0], niz[i][1]);

            rez = min(rez, dist[0][n] + d + dist[1][1]);

        }
    }

    cout << (rez >= inf ? -1 : rez);

    return 0;
}
/**

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1


4 4
1 2 1 0
2 3 1 0
2 4 3 0
3 4 2 0

// probati bojenje sahovski ili slicno

**/

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:126:13: warning: unused variable 'u' [-Wunused-variable]
  126 |         int u = niz[i][0];
      |             ^
ho_t4.cpp:128:13: warning: unused variable 'c' [-Wunused-variable]
  128 |         int c = niz[i][2];
      |             ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1820 KB Output is correct
2 Correct 27 ms 1796 KB Output is correct
3 Correct 31 ms 1720 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 22 ms 1672 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -