Submission #773303

#	Time	Username	Problem	Language	Result	Execution time	Memory
773303		mcdx9524	Robot (JOI21_ho_t4)	C++17	24 / 100	224 ms	21260 KiB

Main

#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
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42