oj.uz

Submission #658701

# Submission time Handle Problem Language Result Execution time Memory
658701 2022-11-14T12:58:06 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
35 / 100
 3409 ms 94796 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;

int n, m, k;
int szrt[maxn], idrt[maxn], thrt[maxn], isrt[maxn], nxrt[maxn], pvrt[maxn], dlol[maxn];
vector<int> g[maxn], d[maxn];

int32_t main() {
    // freopen("in.in", "r", stdin);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> szrt[i];
        for(int j = 0; j < szrt[i]; j++) {
            int v; cin >> v;
            idrt[v] = i;
            isrt[v] = 1;
            thrt[v] = j;
        }
    }

    szrt[0] = 1;
    for(int i = 1; i <= n; i++) {
        dlol[i] = inf;
        if(isrt[i]) {
            for(int j = 0; j < szrt[idrt[i]]; j++) {
                d[i].pb(inf);
            }
            int u = i;
            for(auto v : g[u]) {
                if(isrt[v] && idrt[u] == idrt[v] && thrt[v] == (thrt[u]+1)%szrt[idrt[u]]) {
                    nxrt[u] = v;
                }
                if(isrt[v] && idrt[u] == idrt[v] && thrt[u] == (thrt[v]+1)%szrt[idrt[u]]) {
                    pvrt[u] = v;
                }
            }
        }
        else {
            d[i].pb(inf);
        }

    }

    d[1][0] = 0;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    pq.push(mp(0,mp(1,0)));
    while(pq.size()) {
        int u = pq.top().sc.fr;
        int t = pq.top().sc.sc;
        int dist = pq.top().fr;
        pq.pop();

        if(t != -1 && dist != d[u][t]) continue;
        if(t == -1 && dist != dlol[u]) continue;

        if(t == -1) {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    int d1 = dlol[u]+1;
                    int t1 = d1%szrt[idrt[v]];
                    // Vou encontrar o guarda em v ou indo para v
                    // indo para v == u é depois de v e em t1 ele vai estar em u
                    if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }

                    if(idrt[v] != idrt[u]) {
                        set<int> stt1;
                        d1 = dlol[u]+1;
                        while(true) {
                            int t1 = d1%szrt[idrt[v]];
                            if(stt1.count(t1)) break;
                            stt1.insert(t1);
                            // Vou encontrar o guarda em v ou indo para v
                            // indo para v == u é depois de v e em t1 ele vai estar em u
                            if(t1 == thrt[v]) continue;
                            if(d[v][t1] > d1) {
                                d[v][t1] = d1;
                                pq.push(mp(d[v][t1],mp(v,t1)));
                            }
                            d1+= szrt[idrt[u]];
                        }
                    }
                }
                else {
                    int d1 = dlol[u]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
            continue;
        }

        if(isrt[u]) {
            int v,d1,t1;
            v = nxrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
            }

            v = pvrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
            }

            if(dlol[u] > d[u][t]) {
                dlol[u] = d[u][t];
                pq.push(mp(dlol[u],mp(u,-1)));
            }

            v = u;
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            if(!(t1 == thrt[v]) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
            }
        }
        else {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    // d[u][t]+1+i = (thrt[v]+1) MOD
                    // i = trrt[v]-d[u][t] MOD
                    int i = ((thrt[v]-d[u][t])%szrt[idrt[v]]+szrt[idrt[v]])%szrt[idrt[v]];
                    int d1 = d[u][t]+1+i;
                    int t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                    d1 = d[u][t]+1;
                    t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
                else {
                    int d1 = d[u][t]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
        }
    }

    if(d[n][0] == inf) cout << "impossible" << endl;
    else cout << d[n][0] << endl;
}

Compilation message

watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:80:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |                     if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15380 KB Output is correct
2 Correct 102 ms 22504 KB Output is correct
3 Correct 120 ms 22020 KB Output is correct
4 Correct 115 ms 21964 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 129 ms 21828 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15308 KB Output is correct
2 Correct 130 ms 22488 KB Output is correct
3 Correct 121 ms 22020 KB Output is correct
4 Correct 107 ms 21992 KB Output is correct
5 Correct 11 ms 14420 KB Output is correct
6 Correct 121 ms 21848 KB Output is correct
7 Correct 116 ms 21796 KB Output is correct
8 Correct 129 ms 21808 KB Output is correct
9 Correct 110 ms 21836 KB Output is correct
10 Correct 100 ms 22144 KB Output is correct
11 Correct 106 ms 21984 KB Output is correct
12 Correct 137 ms 21824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15308 KB Output is correct
2 Correct 130 ms 22488 KB Output is correct
3 Correct 121 ms 22020 KB Output is correct
4 Correct 107 ms 21992 KB Output is correct
5 Correct 11 ms 14420 KB Output is correct
6 Correct 121 ms 21848 KB Output is correct
7 Correct 116 ms 21796 KB Output is correct
8 Correct 129 ms 21808 KB Output is correct
9 Correct 110 ms 21836 KB Output is correct
10 Correct 100 ms 22144 KB Output is correct
11 Correct 106 ms 21984 KB Output is correct
12 Correct 137 ms 21824 KB Output is correct
13 Correct 58 ms 15324 KB Output is correct
14 Correct 126 ms 22496 KB Output is correct
15 Correct 113 ms 21984 KB Output is correct
16 Correct 139 ms 22104 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 118 ms 21904 KB Output is correct
19 Correct 109 ms 21904 KB Output is correct
20 Correct 111 ms 21908 KB Output is correct
21 Correct 128 ms 21892 KB Output is correct
22 Correct 112 ms 22148 KB Output is correct
23 Correct 103 ms 21896 KB Output is correct
24 Correct 101 ms 21816 KB Output is correct
25 Correct 2719 ms 66156 KB Output is correct
26 Correct 2495 ms 71304 KB Output is correct
27 Correct 2612 ms 66920 KB Output is correct
28 Correct 2270 ms 70824 KB Output is correct
29 Correct 2567 ms 61352 KB Output is correct
30 Correct 2401 ms 64764 KB Output is correct
31 Correct 2693 ms 71316 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15308 KB Output is correct
2 Correct 130 ms 22488 KB Output is correct
3 Correct 121 ms 22020 KB Output is correct
4 Correct 107 ms 21992 KB Output is correct
5 Correct 11 ms 14420 KB Output is correct
6 Correct 121 ms 21848 KB Output is correct
7 Correct 116 ms 21796 KB Output is correct
8 Correct 129 ms 21808 KB Output is correct
9 Correct 110 ms 21836 KB Output is correct
10 Correct 100 ms 22144 KB Output is correct
11 Correct 106 ms 21984 KB Output is correct
12 Correct 137 ms 21824 KB Output is correct
13 Correct 58 ms 15324 KB Output is correct
14 Correct 126 ms 22496 KB Output is correct
15 Correct 113 ms 21984 KB Output is correct
16 Correct 139 ms 22104 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 118 ms 21904 KB Output is correct
19 Correct 109 ms 21904 KB Output is correct
20 Correct 111 ms 21908 KB Output is correct
21 Correct 128 ms 21892 KB Output is correct
22 Correct 112 ms 22148 KB Output is correct
23 Correct 103 ms 21896 KB Output is correct
24 Correct 101 ms 21816 KB Output is correct
25 Correct 2719 ms 66156 KB Output is correct
26 Correct 2495 ms 71304 KB Output is correct
27 Correct 2612 ms 66920 KB Output is correct
28 Correct 2270 ms 70824 KB Output is correct
29 Correct 2567 ms 61352 KB Output is correct
30 Correct 2401 ms 64764 KB Output is correct
31 Correct 2693 ms 71316 KB Output is correct
32 Correct 44 ms 15308 KB Output is correct
33 Correct 136 ms 22412 KB Output is correct
34 Correct 127 ms 22000 KB Output is correct
35 Correct 144 ms 22124 KB Output is correct
36 Correct 12 ms 14420 KB Output is correct
37 Correct 126 ms 21864 KB Output is correct
38 Correct 101 ms 21880 KB Output is correct
39 Correct 103 ms 21816 KB Output is correct
40 Correct 111 ms 21880 KB Output is correct
41 Correct 118 ms 22052 KB Output is correct
42 Correct 108 ms 22052 KB Output is correct
43 Correct 103 ms 21908 KB Output is correct
44 Correct 2721 ms 65996 KB Output is correct
45 Correct 2467 ms 71224 KB Output is correct
46 Correct 2607 ms 67012 KB Output is correct
47 Correct 2274 ms 70820 KB Output is correct
48 Correct 2610 ms 61460 KB Output is correct
49 Correct 2856 ms 65088 KB Output is correct
50 Correct 2973 ms 71572 KB Output is correct
51 Correct 3179 ms 80236 KB Output is correct
52 Correct 3409 ms 94796 KB Output is correct
53 Correct 2984 ms 78692 KB Output is correct
54 Correct 2202 ms 64528 KB Output is correct
55 Correct 2992 ms 80916 KB Output is correct
56 Correct 2853 ms 70996 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15380 KB Output is correct
2 Correct 102 ms 22504 KB Output is correct
3 Correct 120 ms 22020 KB Output is correct
4 Correct 115 ms 21964 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 129 ms 21828 KB Output is correct
7 Correct 42 ms 15308 KB Output is correct
8 Correct 130 ms 22488 KB Output is correct
9 Correct 121 ms 22020 KB Output is correct
10 Correct 107 ms 21992 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 121 ms 21848 KB Output is correct
13 Correct 116 ms 21796 KB Output is correct
14 Correct 129 ms 21808 KB Output is correct
15 Correct 110 ms 21836 KB Output is correct
16 Correct 100 ms 22144 KB Output is correct
17 Correct 106 ms 21984 KB Output is correct
18 Correct 137 ms 21824 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 10 ms 14420 KB Output is correct
21 Correct 8 ms 14396 KB Output is correct
22 Correct 45 ms 15452 KB Output is correct
23 Correct 128 ms 22652 KB Output is correct
24 Correct 138 ms 22168 KB Output is correct
25 Correct 125 ms 22168 KB Output is correct
26 Correct 10 ms 14392 KB Output is correct
27 Correct 114 ms 22032 KB Output is correct
28 Correct 120 ms 21952 KB Output is correct
29 Correct 99 ms 22032 KB Output is correct
30 Correct 120 ms 21952 KB Output is correct
31 Correct 114 ms 22268 KB Output is correct
32 Correct 112 ms 21992 KB Output is correct
33 Correct 114 ms 22068 KB Output is correct
34 Correct 2735 ms 66232 KB Output is correct
35 Correct 2767 ms 62800 KB Output is correct
36 Correct 2919 ms 62652 KB Output is correct
37 Incorrect 2640 ms 67916 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15380 KB Output is correct
2 Correct 102 ms 22504 KB Output is correct
3 Correct 120 ms 22020 KB Output is correct
4 Correct 115 ms 21964 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 129 ms 21828 KB Output is correct
7 Correct 42 ms 15308 KB Output is correct
8 Correct 130 ms 22488 KB Output is correct
9 Correct 121 ms 22020 KB Output is correct
10 Correct 107 ms 21992 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 121 ms 21848 KB Output is correct
13 Correct 116 ms 21796 KB Output is correct
14 Correct 129 ms 21808 KB Output is correct
15 Correct 110 ms 21836 KB Output is correct
16 Correct 100 ms 22144 KB Output is correct
17 Correct 106 ms 21984 KB Output is correct
18 Correct 137 ms 21824 KB Output is correct
19 Correct 58 ms 15324 KB Output is correct
20 Correct 126 ms 22496 KB Output is correct
21 Correct 113 ms 21984 KB Output is correct
22 Correct 139 ms 22104 KB Output is correct
23 Correct 10 ms 14420 KB Output is correct
24 Correct 118 ms 21904 KB Output is correct
25 Correct 109 ms 21904 KB Output is correct
26 Correct 111 ms 21908 KB Output is correct
27 Correct 128 ms 21892 KB Output is correct
28 Correct 112 ms 22148 KB Output is correct
29 Correct 103 ms 21896 KB Output is correct
30 Correct 101 ms 21816 KB Output is correct
31 Correct 2719 ms 66156 KB Output is correct
32 Correct 2495 ms 71304 KB Output is correct
33 Correct 2612 ms 66920 KB Output is correct
34 Correct 2270 ms 70824 KB Output is correct
35 Correct 2567 ms 61352 KB Output is correct
36 Correct 2401 ms 64764 KB Output is correct
37 Correct 2693 ms 71316 KB Output is correct
38 Correct 8 ms 14420 KB Output is correct
39 Correct 10 ms 14420 KB Output is correct
40 Correct 8 ms 14396 KB Output is correct
41 Correct 45 ms 15452 KB Output is correct
42 Correct 128 ms 22652 KB Output is correct
43 Correct 138 ms 22168 KB Output is correct
44 Correct 125 ms 22168 KB Output is correct
45 Correct 10 ms 14392 KB Output is correct
46 Correct 114 ms 22032 KB Output is correct
47 Correct 120 ms 21952 KB Output is correct
48 Correct 99 ms 22032 KB Output is correct
49 Correct 120 ms 21952 KB Output is correct
50 Correct 114 ms 22268 KB Output is correct
51 Correct 112 ms 21992 KB Output is correct
52 Correct 114 ms 22068 KB Output is correct
53 Correct 2735 ms 66232 KB Output is correct
54 Correct 2767 ms 62800 KB Output is correct
55 Correct 2919 ms 62652 KB Output is correct
56 Incorrect 2640 ms 67916 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15380 KB Output is correct
2 Correct 102 ms 22504 KB Output is correct
3 Correct 120 ms 22020 KB Output is correct
4 Correct 115 ms 21964 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 129 ms 21828 KB Output is correct
7 Correct 42 ms 15308 KB Output is correct
8 Correct 130 ms 22488 KB Output is correct
9 Correct 121 ms 22020 KB Output is correct
10 Correct 107 ms 21992 KB Output is correct
11 Correct 11 ms 14420 KB Output is correct
12 Correct 121 ms 21848 KB Output is correct
13 Correct 116 ms 21796 KB Output is correct
14 Correct 129 ms 21808 KB Output is correct
15 Correct 110 ms 21836 KB Output is correct
16 Correct 100 ms 22144 KB Output is correct
17 Correct 106 ms 21984 KB Output is correct
18 Correct 137 ms 21824 KB Output is correct
19 Correct 58 ms 15324 KB Output is correct
20 Correct 126 ms 22496 KB Output is correct
21 Correct 113 ms 21984 KB Output is correct
22 Correct 139 ms 22104 KB Output is correct
23 Correct 10 ms 14420 KB Output is correct
24 Correct 118 ms 21904 KB Output is correct
25 Correct 109 ms 21904 KB Output is correct
26 Correct 111 ms 21908 KB Output is correct
27 Correct 128 ms 21892 KB Output is correct
28 Correct 112 ms 22148 KB Output is correct
29 Correct 103 ms 21896 KB Output is correct
30 Correct 101 ms 21816 KB Output is correct
31 Correct 2719 ms 66156 KB Output is correct
32 Correct 2495 ms 71304 KB Output is correct
33 Correct 2612 ms 66920 KB Output is correct
34 Correct 2270 ms 70824 KB Output is correct
35 Correct 2567 ms 61352 KB Output is correct
36 Correct 2401 ms 64764 KB Output is correct
37 Correct 2693 ms 71316 KB Output is correct
38 Correct 44 ms 15308 KB Output is correct
39 Correct 136 ms 22412 KB Output is correct
40 Correct 127 ms 22000 KB Output is correct
41 Correct 144 ms 22124 KB Output is correct
42 Correct 12 ms 14420 KB Output is correct
43 Correct 126 ms 21864 KB Output is correct
44 Correct 101 ms 21880 KB Output is correct
45 Correct 103 ms 21816 KB Output is correct
46 Correct 111 ms 21880 KB Output is correct
47 Correct 118 ms 22052 KB Output is correct
48 Correct 108 ms 22052 KB Output is correct
49 Correct 103 ms 21908 KB Output is correct
50 Correct 2721 ms 65996 KB Output is correct
51 Correct 2467 ms 71224 KB Output is correct
52 Correct 2607 ms 67012 KB Output is correct
53 Correct 2274 ms 70820 KB Output is correct
54 Correct 2610 ms 61460 KB Output is correct
55 Correct 2856 ms 65088 KB Output is correct
56 Correct 2973 ms 71572 KB Output is correct
57 Correct 3179 ms 80236 KB Output is correct
58 Correct 3409 ms 94796 KB Output is correct
59 Correct 2984 ms 78692 KB Output is correct
60 Correct 2202 ms 64528 KB Output is correct
61 Correct 2992 ms 80916 KB Output is correct
62 Correct 2853 ms 70996 KB Output is correct
63 Correct 8 ms 14420 KB Output is correct
64 Correct 10 ms 14420 KB Output is correct
65 Correct 8 ms 14396 KB Output is correct
66 Correct 45 ms 15452 KB Output is correct
67 Correct 128 ms 22652 KB Output is correct
68 Correct 138 ms 22168 KB Output is correct
69 Correct 125 ms 22168 KB Output is correct
70 Correct 10 ms 14392 KB Output is correct
71 Correct 114 ms 22032 KB Output is correct
72 Correct 120 ms 21952 KB Output is correct
73 Correct 99 ms 22032 KB Output is correct
74 Correct 120 ms 21952 KB Output is correct
75 Correct 114 ms 22268 KB Output is correct
76 Correct 112 ms 21992 KB Output is correct
77 Correct 114 ms 22068 KB Output is correct
78 Correct 2735 ms 66232 KB Output is correct
79 Correct 2767 ms 62800 KB Output is correct
80 Correct 2919 ms 62652 KB Output is correct
81 Incorrect 2640 ms 67916 KB Output isn't correct
82 Halted 0 ms 0 KB -