oj.uz

Submission #59639

# Submission time Handle Problem Language Result Execution time Memory
59639 2018-07-22T20:22:20 Z Benq Cities (BOI16_cities) C++11
100 / 100
 1764 ms 68180 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int n,k,m;
ll sh[5][MX], bes[5][5][MX];
vi imp;

template<int SZ> struct Dijkstra {
    ll dist[SZ];
    vpi adj[SZ];
    priority_queue<pl,vpl,greater<pl>> q;
    
    void addEdge(int a, int b, int c) {
        adj[a].pb({b,c}), adj[b].pb({a,c});
    }
    
    void clr(int x) {
        FOR(i,1,n+1) dist[i] = INF;
        while (sz(q)) q.pop();
        q.push({dist[x] = 0,x});
    }
    
    void clr(int x, int y) {
        while (sz(q)) q.pop();
        FOR(i,1,n+1) q.push({dist[i] = sh[x][i]+sh[y][i],i});
    }
    
    void gen() {
        while (sz(q)) {
            pl x = q.top(); q.pop();
            if (dist[x.s] < x.f) continue;
            for (pi y: adj[x.s]) if (x.f+y.s < dist[y.f])
                q.push({dist[y.f] = x.f+y.s,y.f});
        }
    }
};

Dijkstra<MX> D;

void genPath(int x) {
    D.clr(imp[x]);
    D.gen();
    FOR(i,1,n+1) sh[x][i] = D.dist[i];
}

void genBes(int x, int y) {
    D.clr(x,y);
    D.gen();
    FOR(i,1,n+1) bes[x][y][i] = D.dist[i];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m; imp.resize(k);
    F0R(i,k) cin >> imp[i];
    while (sz(imp) < 5) imp.pb(imp.front());
    k = 5;
    
    F0R(i,m) {
        int a,b,c; cin >> a >> b >> c;
        D.addEdge(a,b,c);
    }
    F0R(i,k) genPath(i);
    // cout << sh[1][1];
    F0R(i,k) FOR(j,i+1,k) genBes(i,j);

    ll ans = INF;
    FOR(i,1,n+1) F0R(j,k) {
        int x = (j == 0);
        FOR(z,x+1,k) if (z != j) {
            int X = -1, Z = -1;
            F0R(I,k) if (I != j && I != x && I != z) {
                if (X == -1) X = I;
                else Z = I;
            }
            ans = min(ans,sh[j][i]+bes[x][z][i]+bes[X][Z][i]);
        }
    }
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 5 ms 2876 KB Output is correct
3 Correct 5 ms 2876 KB Output is correct
4 Correct 4 ms 2876 KB Output is correct
5 Correct 6 ms 3012 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 24336 KB Output is correct
2 Correct 1660 ms 28468 KB Output is correct
3 Correct 918 ms 28468 KB Output is correct
4 Correct 121 ms 28468 KB Output is correct
5 Correct 1340 ms 38524 KB Output is correct
6 Correct 133 ms 38524 KB Output is correct
7 Correct 12 ms 38524 KB Output is correct
8 Correct 13 ms 38524 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 38524 KB Output is correct
2 Correct 12 ms 38524 KB Output is correct
3 Correct 7 ms 38524 KB Output is correct
4 Correct 10 ms 38524 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 42004 KB Output is correct
2 Correct 1462 ms 46380 KB Output is correct
3 Correct 1096 ms 46380 KB Output is correct
4 Correct 889 ms 46380 KB Output is correct
5 Correct 259 ms 46380 KB Output is correct
6 Correct 154 ms 46380 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1758 ms 60136 KB Output is correct
2 Correct 1764 ms 64196 KB Output is correct
3 Correct 1236 ms 68180 KB Output is correct
4 Correct 1261 ms 68180 KB Output is correct
5 Correct 884 ms 68180 KB Output is correct
6 Correct 280 ms 68180 KB Output is correct
7 Correct 129 ms 68180 KB Output is correct