oj.uz

Submission #773303

# Submission time Handle Problem Language Result Execution time Memory
773303 2023-07-04T20:30:54 Z mcdx9524 Robot (JOI21_ho_t4) C++17
24 / 100
 224 ms 21260 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <vector <pair <int, int> > > g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--, b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector <vector <pair <int, int> > > cg(n);
    map <int, int> color_cnt;
    for (int i = 0; i < n; i++) {
        vector <pair <int, int> > cols;
        for (auto [v, c] : g[i]) {
            cols.push_back({c, v});
            color_cnt[c]++;
        }
        sort(cols.begin(), cols.end());
        for (int j = 0; j < (int) cols.size(); j++) {
            bool alone = true;
            if (j >= 0 && cols[j - 1].first == cols[j].first) {
                alone = false;
            }
            if (j + 1 < (int) cols.size() && cols[j + 1].first == cols[j].first) {
                alone = false;
            }
            if (alone) {
                cg[i].push_back({cols[j].second, 0});
            } else {
                cg[i].push_back({cols[j].second, 1});
            }
        }
        for (int j = 1; j < (int) cols.size(); j++) {
            if (cols[j].first == cols[j - 1].first && color_cnt[cols[j].first] == 2) {
                cg[cols[j - 1].second].push_back({cols[j].second, 1});
                cg[cols[j].second].push_back({cols[j - 1].second, 1});
            }
        }
        for (auto [v, c] : g[i]) {
            color_cnt[c]--;
        }
    }
    vector <int> d(n, inf);
    deque <int> q;
    q.push_front(0);
    d[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto [to, c] : cg[v]) {
            if (d[to] > d[v] + c) {
                d[to] = d[v] + c;
                if (c == 0) {
                    q.push_front(to);
                } else {
                    q.push_back(to);
                }
            }
        }
    }
    cout << (d[n - 1] == inf ? -1 : d[n - 1]) << '\n';
    return 0;
}

Subtask #1
0 / 34.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6364 KB Output is correct
2 Correct 19 ms 3412 KB Output is correct
3 Correct 56 ms 7820 KB Output is correct
4 Correct 27 ms 4852 KB Output is correct
5 Correct 224 ms 21248 KB Output is correct
6 Correct 195 ms 21260 KB Output is correct
7 Correct 116 ms 20688 KB Output is correct
8 Correct 101 ms 21044 KB Output is correct
9 Correct 101 ms 21064 KB Output is correct
10 Correct 68 ms 13288 KB Output is correct
11 Correct 59 ms 13032 KB Output is correct

Subtask #3
0 / 42.0

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