oj.uz

Submission #718738

# Submission time Handle Problem Language Result Execution time Memory
718738 2023-04-04T15:42:49 Z tcmmichaelb139 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 49416 KB 
#include "bits/stdc++.h"
using namespace std;

const int MAXN = 100001;

long long dist[MAXN][2];

struct node {
    int v;
    long long c;
    int p;
    bool chgd;
    bool operator<(const node &rhs) const {
        return dist[v][chgd] > dist[rhs.v][rhs.chgd];
    }
};

int n, m;
vector<pair<int, pair<int, long long>>> adj[MAXN];
int vis[MAXN][2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        long long d;
        cin >> a >> b >> c >> d;
        adj[a].push_back({b, {c, d}});
        adj[b].push_back({a, {c, d}});
    }

    for (int i = 0; i <= n; i++)
        dist[i][0] = dist[i][1] = 1e18;
    dist[1][0] = 0;

    priority_queue<node> q;
    q.push({1, 0, -1, 0});
    while (!q.empty()) {
        node v = q.top();
        q.pop();

        if (vis[v.v][v.chgd]) {
            map<int, long long> cols;

            for (auto u : adj[v.v]) {
                if (!v.chgd || u.first != v.p)
                    cols[u.second.first] += u.second.second;
                if (vis[u.first][1]) continue;
                dist[u.first][1] = min(dist[u.first][1], v.c + u.second.second);
            }

            for (auto u : adj[v.v]) {
                if (vis[u.first][0]) continue;
                dist[u.first][0] = min(dist[u.first][0], v.c + cols[u.second.first] - u.second.second);
            }
            continue;
        }
        vis[v.v][v.chgd] = true;

        map<int, long long> cols;

        for (auto u : adj[v.v]) {
            if (!v.chgd || u.first != v.p)
                cols[u.second.first] += u.second.second;
            if (vis[u.first][1]) continue;
            dist[u.first][1] = min(dist[u.first][1], dist[v.v][v.chgd] + u.second.second);
            q.push({u.first, dist[v.v][v.chgd] + u.second.second, v.v, true});
        }

        for (auto u : adj[v.v]) {
            if (vis[u.first][0]) continue;
            dist[u.first][0] = min(dist[u.first][0], dist[v.v][v.chgd] + cols[u.second.first] - u.second.second);
            q.push({u.first, dist[v.v][v.chgd] + cols[u.second.first] - u.second.second, v.v, false});
        }
    }
    cout << min(dist[n][0], dist[n][1]) << '\n';
}

Subtask #1
0 / 34.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 16816 KB Output is correct
2 Correct 72 ms 9400 KB Output is correct
3 Correct 408 ms 28504 KB Output is correct
4 Correct 109 ms 11200 KB Output is correct
5 Execution timed out 3078 ms 49416 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

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