Submission #680916

#	Time	Username	Problem	Language	Result	Execution time	Memory
680916		DennisTran	Relay Marathon (NOI20_relaymarathon)	C++17	25 / 100	4538 ms	73632 KiB

RelayMarathon

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 1e9 + 7;

int N, M, K;
vector <ii> ke[MAXN];
vector <int> Special;

struct SUB2{
    int dist[505], C[505][505];
    vector <vector <ii>> Dist;
    void Dijsktra(int id) {
        FOR(i, 1, N) dist[i] = INF;
        priority_queue <ii, vector <ii>, greater <ii>> q;
        q.emplace(dist[Special[id]] = 0, Special[id]);
        while (q.size()) {
            int du = q.top().fi, u = q.top().se; q.pop();
            if (du != dist[u]) continue;
            for (ii x : ke[u]) {
                int v = x.fi, w = x.se;
                if (dist[v] > du + w) {
                    dist[v] = du + w;
                    q.emplace(du + w, v);
                }
            }
        }
        FOR(i, 1, N) C[id][i] = dist[i];
        for (int x : Special) if (x != Special[id])
            Dist[id].emplace_back(dist[x], x);
    }

    void solve() {
        if (N > 500) return;
        Dist.resize(K);
        REP(i, K) Dijsktra(i);
        int ans = INF;
        REP(i, K) REP(j, K) if (i != j && C[i][Special[j]] != INF)
            REP(t, K) if (i != t && j != t) {
                int tmp = C[i][Special[j]];
                for (ii x : Dist[t]) if (x.se != Special[i] && x.se != Special[j]) {
                    tmp += x.fi;
                    break;
                }
                ans = min(ans, tmp);
            }
        cout << ans;
        exit(0);
    }
}sub2;

struct SUB3{
    bool dd[MAXN];
    vector <int> Gate;
    ii ans[MAXN];
    int dist[MAXN], trace[MAXN];
    void Dijsktra(int k, int c) {
        priority_queue <ii, vector <ii>, greater <ii>> q;
        FOR(i, 1, N) dist[i] = 1e18, trace[i] = 0;
        for (auto x : Gate) if (((x >> k) & 1) == c)
            q.emplace(dist[x] = 0, x), trace[x] = x;


        while (q.size()) {
            long long du = q.top().fi;
            int u = q.top().se;
            q.pop();
            if (du != dist[u]) continue;
            for (auto x : ke[u]) {
                int v = x.fi, w = x.se;
                if (dist[v] > du + w) {
                    dist[v] = du + w;
                    trace[v] = trace[u];
                    q.emplace(du + w, v);
                } else if (dist[v] == du + w) {
                    if (trace[v] > trace[u]) {
                        trace[v] = trace[u];
                        q.emplace(du + w, v);
                    }
                }
            }
        }

        for (auto x : Gate) if (((x >> k) & 1) != c)
            ans[x] = min(ans[x], {dist[x], trace[x]});
    }
    void solve() {
        bool ok = 0;
        for (int x : Special) dd[x] = 1;
        for (int x : Special)
            if (ke[x].size() == 1 && dd[ke[x][0].fi] && ke[x][0].se == 1) {
                if (ke[ke[x][0].fi].size() != 1) continue;
                dd[x] = dd[ke[x][0].fi] = 0;
                ok = 1;
                break;
            }
        if (!ok) return;
        for (int x : Special) if (dd[x]) Gate.emplace_back(x);
        for (int x : Gate) ans[x] = {INF, -1};
        FOD(i, 18, 0) REP(c, 2)
            Dijsktra(i, c);
        int res = INF;
        for (int x : Gate) res = min(res, ans[x].fi);
        cout << res + 1; exit(0);
    }
}sub3;

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //file("TASK");
    cin >> N >> M >> K;
    while (M--) {
        int u, v, w; cin >> u >> v >> w;
        ke[u].emplace_back(v, w);
        ke[v].emplace_back(u, w);
    }
    Special.resize(K);
    for (int &x : Special) cin >> x;
    sub2.solve();
    sub3.solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

RelayMarathon.cpp: In member function 'void SUB3::Dijsktra(int, int)':
RelayMarathon.cpp:71:32: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   71 |         FOR(i, 1, N) dist[i] = 1e18, trace[i] = 0;
      |                                ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 58