Submission #408869

#	Time	Username	Problem	Language	Result	Execution time	Memory
408869		ly20	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	272 ms	42976 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 512345;
const long long INF = 1123456789012345678;
vector <int> grafo[MAXN];
long long dist[MAXN];
vector <int> cic[MAXN];
int inv[MAXN], pos[MAXN], tam[MAXN];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b); a--; b--;
        grafo[a].push_back(b); grafo[b].push_back(a);
    }
    set <pair <long long, int> > s;
    for(int i = 0; i < 2 * n; i++) {
            inv[i] = -1;
        dist[i] = INF;
        dist[0] = 0;
        s.insert(make_pair(dist[i], i));
    }
    int k;
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        int l;
        scanf("%d", &l);
        for(int j = 0; j < l; j++) {
            int a;
            scanf("%d", &a); a--;
            cic[i].push_back(a);
            inv[a] = i; pos[a] = j; tam[a] = l;
        }
    }
    while(!s.empty()) {
        int cur = (*s.begin()).second;
        //printf("%d\n", cur);
        s.erase(s.begin());
        int rep = cur / 2;
        int d = dist[cur];
        for(int i = 0; i < grafo[rep].size(); i++) {
            int viz = grafo[rep][i];
            //printf("%d\n", viz);
            int t1 = 2 * viz, t2 = 2 * viz + 1;
            int m1 = d + 1, m2 = d + 1;
            if(inv[viz] != -1 && inv[viz] == inv[rep]) {
                if(d % tam[viz] == pos[viz] && (d + 1) % tam[viz] == pos[rep]) continue;
            }
            if(inv[viz] == -1 && dist[t1] > m1) {
                s.erase(make_pair(dist[t1], t1));
                dist[t1] = m1;
                s.insert(make_pair(dist[t1], t1));
            }
            else if(inv[viz] != -1) {
                int c = inv[viz], tm = tam[viz];
                if(cic[c][m1 % tm] == viz) m1++;
                if(dist[t1] > m1) {
                    s.erase(make_pair(dist[t1], t1));
                    dist[t1] = m1;
                    s.insert(make_pair(dist[t1], t1));
                }
                int pr = (pos[viz] + 1) % tm;
                if(m2 % tm <= pr) m2 += pr - (m2 % tm);
                else m2 += pr - (m2 % tm) + n;
                if(dist[t2] > m2 && cic[inv[viz]][pr] != viz) {
                    s.erase(make_pair(dist[t2], t2));
                    dist[t2] = m2;
                    s.insert(make_pair(dist[t2], t2));
                }
            }
            //printf("oi\n");
        }
    }
    if(dist[2 * n - 2] < INF) printf("%lld\n", dist[2 * n - 2]);
    else printf("impossible\n");
    return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < grafo[rep].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d", &a, &b); a--; b--;
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d", &l);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d", &a); a--;
      |             ~~~~~^~~~~~~~~~

• 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