Submission #1041533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041533		Plurm	From Hacks to Snitches (BOI21_watchmen)	C++11	0 / 100	24 ms	13596 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;

vector<int> g[250005];
int cnum[250005];
int cidx[250005];
int dist[250005];
vector<vector<int>> cyc;
int main() {
    memset(dist, 0x3f, sizeof(dist));
    memset(cnum, -1, sizeof(cnum));
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int l;
        cin >> l;
        cyc.push_back({});
        for (int j = 0; j < l; j++) {
            int x;
            cin >> x;
            cnum[x] = i;
            cidx[x] = j;
            cyc.back().push_back(x);
        }
    }
    priority_queue<pair<int, int>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int o = -p.first;
        // cout << "DBG " << o << " " << p.second << endl;
        if (cnum[p.second] != -1) {
            int base = cidx[p.second];
            int l = cyc[cnum[p.second]].size();
            int j = (o + l - base) % l;
            for (int ii = 0; ii < l; ii++) {
                int i = (ii + l - base) % l;
                int d = min(i, l + j < 2 * i   ? l - i
                               : 1 + l < 2 * i ? 2 * l - i - j + 1
                                               : 1000000000);
                // cout << "DELTA " << i << " " << j << " " << d << endl;
                if (o + d < dist[cyc[cnum[p.second]][ii]]) {
                    dist[cyc[cnum[p.second]][ii]] = o + d;
                    pq.push({-(o + d), cyc[cnum[p.second]][ii]});
                }
            }
            for (int v : g[p.second]) {
                if (cnum[v] == cnum[p.second]) {
                    if ((cidx[v] + 1) % l == base)
                        continue;
                    int wait = 0;
                    if ((o + 1) % l == cidx[v])
                        wait++;
                    if (o + 1 + wait < dist[v]) {
                        dist[v] = o + 1 + wait;
                        pq.push({-(o + 1 + wait), v});
                    }
                } else if (cnum[v] != -1) {
                    throw 0;
                } else {
                    if (o + 1 < dist[v]) {
                        dist[v] = o + 1;
                        pq.push({-(o + 1), v});
                    }
                }
            }
        } else {
            for (int v : g[p.second]) {
                int wait = 0;
                if (cnum[v] != -1 && cidx[v] == (o + 1) % cyc[cnum[v]].size())
                    wait++;
                if (o + 1 + wait < dist[v]) {
                    dist[v] = o + 1 + wait;
                    pq.push({-(o + 1 + wait), v});
                }
            }
        }
    }
    if (dist[n] >= 1e9)
        cout << "impossible" << endl;
    else
        cout << dist[n] << endl;
    return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:82:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (cnum[v] != -1 && cidx[v] == (o + 1) % cyc[cnum[v]].size())
      |                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20