oj.uz

Submission #945219

# Submission time Handle Problem Language Result Execution time Memory
945219 2024-03-13T14:36:57 Z May27_th Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 53704 KB 
#include<bits/stdc++.h>
#define taskname "A"
using namespace std;

void World_Final();
void Solve();

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen(taskname".in", "r")) {
        freopen(taskname".in", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    World_Final();
}

void World_Final(){
    int Tests = 1;
    //cin >> Tests;
    for (int i = 1; i <= Tests; i ++) {
        //cout << i << "\n";
        Solve();
    }
}

const int MAXN = 1e5 + 10;
const int64_t INF = 1e18;

int N, M;
struct Edge{ int to, c, p; };
vector<Edge> G[MAXN]; map<int, int64_t> sum[MAXN], f[MAXN];
void Solve(){
    cin >> N >> M; for (int i = 1; i <= M; i ++) {
        int u, v, c, p; cin >> u >> v >> c >> p;
        G[u].push_back({v, c, p});
        G[v].push_back({u, c, p});
        sum[u][c] += p;
        sum[v][c] += p;
    } f[1][0] = 0;
    priority_queue<pair<int64_t, pair<int, int>>> pq; pq.push(make_pair(0, make_pair(1, 0)));
    while (!pq.empty()) {
        int64_t d = pq.top().first;
        int u, prevc; tie(u, prevc) = pq.top().second; pq.pop();
        if (-d != f[u][prevc]) continue;
        for (auto [v, c, p] : G[u]) {
            if (prevc == c) {
                /// Have to flip others because haven't flipped previous edge with same
                /// color c
                if (f[v].find(0) == f[v].end() || f[v][0] > f[u][prevc] + sum[u][prevc] - p) {
                    f[v][0] = f[u][prevc] + sum[u][prevc] - p;
                    pq.push(make_pair(-f[v][0], make_pair(v, 0)));
                }
            } else {
                /// Flip this edge
                if (f[v].find(0) == f[v].end() || f[v][0] > f[u][0] + p) {
                    f[v][0] = f[u][0] + p;
                    pq.push(make_pair(-f[v][0], make_pair(v, 0)));
                }

                /// Flip others
                if (f[v].find(0) == f[v].end() || f[v][0] > f[u][0] + sum[u][c] - p) {
                    f[v][0] = f[u][0] + sum[u][c] - p;
                    pq.push(make_pair(-f[v][0], make_pair(v, 0)));
                }

                /// Save to flip with latter edge
                if (f[v].find(c) == f[v].end() || f[v][c] > f[u][0]) {
                    f[v][c] = f[u][0];
                    pq.push(make_pair(-f[v][c], make_pair(v, c)));
                }
            }
        }
    }
    if (f[N].find(0) == f[N].end()) cout << -1;
    else cout << f[N][0];
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(taskname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 4 ms 12200 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 5 ms 12252 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 74 ms 12644 KB Output is correct
10 Correct 38 ms 12884 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 6 ms 12328 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 6 ms 12380 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 5 ms 12376 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 5 ms 12380 KB Output is correct
20 Correct 4 ms 12424 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 28112 KB Output is correct
2 Correct 50 ms 19960 KB Output is correct
3 Correct 109 ms 25556 KB Output is correct
4 Correct 76 ms 22720 KB Output is correct
5 Execution timed out 3058 ms 53704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 4 ms 12200 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 5 ms 12252 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 74 ms 12644 KB Output is correct
10 Correct 38 ms 12884 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 6 ms 12328 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 6 ms 12380 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 5 ms 12376 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 5 ms 12380 KB Output is correct
20 Correct 4 ms 12424 KB Output is correct
21 Correct 135 ms 28112 KB Output is correct
22 Correct 50 ms 19960 KB Output is correct
23 Correct 109 ms 25556 KB Output is correct
24 Correct 76 ms 22720 KB Output is correct
25 Execution timed out 3058 ms 53704 KB Time limit exceeded
26 Halted 0 ms 0 KB -