oj.uz

Submission #658710

# Submission time Handle Problem Language Result Execution time Memory
658710 2022-11-14T13:16:50 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
35 / 100
 2802 ms 277080 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;
const int maxd = 5e6;

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];
vector<pair<int,pair<int,int>>> withdist[maxd+1];

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;
    withdist[0].pb(mp(0,mp(1,0)));
    for(int distcur = 0; distcur <= maxd; distcur++) {
    while(withdist[distcur].size()) {
        auto X = withdist[distcur].back();
        withdist[distcur].pop_back();
        int u = X.sc.fr;
        int t = X.sc.sc;
        int dist = X.fr;
        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;
                        withdist[d[v][t1]].pb(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(d[v][t1] > d1 && t1 != thrt[v]) {
                                d[v][t1] = d1;
                                withdist[d[v][t1]].pb(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;
                        withdist[d[v][t1]].pb(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;
                withdist[d[v][t1]].pb(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;
                withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
            }

            if(dlol[u] > d[u][t]) {
                dlol[u] = d[u][t];
                withdist[dlol[u]].pb(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;
                withdist[d[v][t1]].pb(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;
                        withdist[d[v][t1]].pb(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;
                        withdist[d[v][t1]].pb(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;
                        withdist[d[v][t1]].pb(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:82:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   82 |                     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 97 ms 133056 KB Output is correct
2 Correct 181 ms 143276 KB Output is correct
3 Correct 161 ms 141796 KB Output is correct
4 Correct 185 ms 141568 KB Output is correct
5 Correct 64 ms 132032 KB Output is correct
6 Correct 157 ms 141684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 132920 KB Output is correct
2 Correct 170 ms 143224 KB Output is correct
3 Correct 169 ms 141820 KB Output is correct
4 Correct 170 ms 141540 KB Output is correct
5 Correct 67 ms 132052 KB Output is correct
6 Correct 166 ms 141608 KB Output is correct
7 Correct 198 ms 141744 KB Output is correct
8 Correct 190 ms 141816 KB Output is correct
9 Correct 160 ms 141888 KB Output is correct
10 Correct 167 ms 141116 KB Output is correct
11 Correct 151 ms 140612 KB Output is correct
12 Correct 163 ms 141544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 132920 KB Output is correct
2 Correct 170 ms 143224 KB Output is correct
3 Correct 169 ms 141820 KB Output is correct
4 Correct 170 ms 141540 KB Output is correct
5 Correct 67 ms 132052 KB Output is correct
6 Correct 166 ms 141608 KB Output is correct
7 Correct 198 ms 141744 KB Output is correct
8 Correct 190 ms 141816 KB Output is correct
9 Correct 160 ms 141888 KB Output is correct
10 Correct 167 ms 141116 KB Output is correct
11 Correct 151 ms 140612 KB Output is correct
12 Correct 163 ms 141544 KB Output is correct
13 Correct 99 ms 132936 KB Output is correct
14 Correct 198 ms 143192 KB Output is correct
15 Correct 176 ms 141772 KB Output is correct
16 Correct 157 ms 141596 KB Output is correct
17 Correct 67 ms 132048 KB Output is correct
18 Correct 173 ms 141520 KB Output is correct
19 Correct 160 ms 141776 KB Output is correct
20 Correct 169 ms 141840 KB Output is correct
21 Correct 160 ms 141956 KB Output is correct
22 Correct 171 ms 141148 KB Output is correct
23 Correct 155 ms 140580 KB Output is correct
24 Correct 164 ms 141412 KB Output is correct
25 Correct 2692 ms 189636 KB Output is correct
26 Correct 2586 ms 196160 KB Output is correct
27 Correct 2472 ms 191604 KB Output is correct
28 Correct 2107 ms 195644 KB Output is correct
29 Correct 2473 ms 183200 KB Output is correct
30 Correct 2432 ms 186808 KB Output is correct
31 Correct 2719 ms 194292 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 132920 KB Output is correct
2 Correct 170 ms 143224 KB Output is correct
3 Correct 169 ms 141820 KB Output is correct
4 Correct 170 ms 141540 KB Output is correct
5 Correct 67 ms 132052 KB Output is correct
6 Correct 166 ms 141608 KB Output is correct
7 Correct 198 ms 141744 KB Output is correct
8 Correct 190 ms 141816 KB Output is correct
9 Correct 160 ms 141888 KB Output is correct
10 Correct 167 ms 141116 KB Output is correct
11 Correct 151 ms 140612 KB Output is correct
12 Correct 163 ms 141544 KB Output is correct
13 Correct 99 ms 132936 KB Output is correct
14 Correct 198 ms 143192 KB Output is correct
15 Correct 176 ms 141772 KB Output is correct
16 Correct 157 ms 141596 KB Output is correct
17 Correct 67 ms 132048 KB Output is correct
18 Correct 173 ms 141520 KB Output is correct
19 Correct 160 ms 141776 KB Output is correct
20 Correct 169 ms 141840 KB Output is correct
21 Correct 160 ms 141956 KB Output is correct
22 Correct 171 ms 141148 KB Output is correct
23 Correct 155 ms 140580 KB Output is correct
24 Correct 164 ms 141412 KB Output is correct
25 Correct 2692 ms 189636 KB Output is correct
26 Correct 2586 ms 196160 KB Output is correct
27 Correct 2472 ms 191604 KB Output is correct
28 Correct 2107 ms 195644 KB Output is correct
29 Correct 2473 ms 183200 KB Output is correct
30 Correct 2432 ms 186808 KB Output is correct
31 Correct 2719 ms 194292 KB Output is correct
32 Correct 99 ms 132916 KB Output is correct
33 Correct 172 ms 143252 KB Output is correct
34 Correct 168 ms 141868 KB Output is correct
35 Correct 158 ms 141552 KB Output is correct
36 Correct 67 ms 132044 KB Output is correct
37 Correct 159 ms 141528 KB Output is correct
38 Correct 162 ms 141768 KB Output is correct
39 Correct 159 ms 141840 KB Output is correct
40 Correct 164 ms 142076 KB Output is correct
41 Correct 160 ms 141152 KB Output is correct
42 Correct 151 ms 140620 KB Output is correct
43 Correct 161 ms 141520 KB Output is correct
44 Correct 2601 ms 189868 KB Output is correct
45 Correct 2545 ms 196104 KB Output is correct
46 Correct 2437 ms 191668 KB Output is correct
47 Correct 2164 ms 195816 KB Output is correct
48 Correct 2480 ms 183324 KB Output is correct
49 Correct 2402 ms 186836 KB Output is correct
50 Correct 2659 ms 194208 KB Output is correct
51 Correct 2802 ms 237276 KB Output is correct
52 Correct 2761 ms 277080 KB Output is correct
53 Correct 2587 ms 238900 KB Output is correct
54 Correct 2135 ms 193684 KB Output is correct
55 Correct 2642 ms 234316 KB Output is correct
56 Correct 2571 ms 213924 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 133056 KB Output is correct
2 Correct 181 ms 143276 KB Output is correct
3 Correct 161 ms 141796 KB Output is correct
4 Correct 185 ms 141568 KB Output is correct
5 Correct 64 ms 132032 KB Output is correct
6 Correct 157 ms 141684 KB Output is correct
7 Correct 98 ms 132920 KB Output is correct
8 Correct 170 ms 143224 KB Output is correct
9 Correct 169 ms 141820 KB Output is correct
10 Correct 170 ms 141540 KB Output is correct
11 Correct 67 ms 132052 KB Output is correct
12 Correct 166 ms 141608 KB Output is correct
13 Correct 198 ms 141744 KB Output is correct
14 Correct 190 ms 141816 KB Output is correct
15 Correct 160 ms 141888 KB Output is correct
16 Correct 167 ms 141116 KB Output is correct
17 Correct 151 ms 140612 KB Output is correct
18 Correct 163 ms 141544 KB Output is correct
19 Correct 68 ms 131792 KB Output is correct
20 Correct 68 ms 131840 KB Output is correct
21 Correct 66 ms 131812 KB Output is correct
22 Correct 100 ms 132968 KB Output is correct
23 Correct 169 ms 143180 KB Output is correct
24 Correct 170 ms 141864 KB Output is correct
25 Correct 157 ms 141548 KB Output is correct
26 Correct 68 ms 132060 KB Output is correct
27 Correct 156 ms 141600 KB Output is correct
28 Correct 166 ms 141768 KB Output is correct
29 Correct 162 ms 141844 KB Output is correct
30 Correct 165 ms 141948 KB Output is correct
31 Correct 161 ms 141196 KB Output is correct
32 Correct 159 ms 140588 KB Output is correct
33 Correct 169 ms 141504 KB Output is correct
34 Correct 2603 ms 186972 KB Output is correct
35 Correct 2682 ms 181752 KB Output is correct
36 Correct 2666 ms 183976 KB Output is correct
37 Incorrect 2436 ms 186840 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 133056 KB Output is correct
2 Correct 181 ms 143276 KB Output is correct
3 Correct 161 ms 141796 KB Output is correct
4 Correct 185 ms 141568 KB Output is correct
5 Correct 64 ms 132032 KB Output is correct
6 Correct 157 ms 141684 KB Output is correct
7 Correct 98 ms 132920 KB Output is correct
8 Correct 170 ms 143224 KB Output is correct
9 Correct 169 ms 141820 KB Output is correct
10 Correct 170 ms 141540 KB Output is correct
11 Correct 67 ms 132052 KB Output is correct
12 Correct 166 ms 141608 KB Output is correct
13 Correct 198 ms 141744 KB Output is correct
14 Correct 190 ms 141816 KB Output is correct
15 Correct 160 ms 141888 KB Output is correct
16 Correct 167 ms 141116 KB Output is correct
17 Correct 151 ms 140612 KB Output is correct
18 Correct 163 ms 141544 KB Output is correct
19 Correct 99 ms 132936 KB Output is correct
20 Correct 198 ms 143192 KB Output is correct
21 Correct 176 ms 141772 KB Output is correct
22 Correct 157 ms 141596 KB Output is correct
23 Correct 67 ms 132048 KB Output is correct
24 Correct 173 ms 141520 KB Output is correct
25 Correct 160 ms 141776 KB Output is correct
26 Correct 169 ms 141840 KB Output is correct
27 Correct 160 ms 141956 KB Output is correct
28 Correct 171 ms 141148 KB Output is correct
29 Correct 155 ms 140580 KB Output is correct
30 Correct 164 ms 141412 KB Output is correct
31 Correct 2692 ms 189636 KB Output is correct
32 Correct 2586 ms 196160 KB Output is correct
33 Correct 2472 ms 191604 KB Output is correct
34 Correct 2107 ms 195644 KB Output is correct
35 Correct 2473 ms 183200 KB Output is correct
36 Correct 2432 ms 186808 KB Output is correct
37 Correct 2719 ms 194292 KB Output is correct
38 Correct 68 ms 131792 KB Output is correct
39 Correct 68 ms 131840 KB Output is correct
40 Correct 66 ms 131812 KB Output is correct
41 Correct 100 ms 132968 KB Output is correct
42 Correct 169 ms 143180 KB Output is correct
43 Correct 170 ms 141864 KB Output is correct
44 Correct 157 ms 141548 KB Output is correct
45 Correct 68 ms 132060 KB Output is correct
46 Correct 156 ms 141600 KB Output is correct
47 Correct 166 ms 141768 KB Output is correct
48 Correct 162 ms 141844 KB Output is correct
49 Correct 165 ms 141948 KB Output is correct
50 Correct 161 ms 141196 KB Output is correct
51 Correct 159 ms 140588 KB Output is correct
52 Correct 169 ms 141504 KB Output is correct
53 Correct 2603 ms 186972 KB Output is correct
54 Correct 2682 ms 181752 KB Output is correct
55 Correct 2666 ms 183976 KB Output is correct
56 Incorrect 2436 ms 186840 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 133056 KB Output is correct
2 Correct 181 ms 143276 KB Output is correct
3 Correct 161 ms 141796 KB Output is correct
4 Correct 185 ms 141568 KB Output is correct
5 Correct 64 ms 132032 KB Output is correct
6 Correct 157 ms 141684 KB Output is correct
7 Correct 98 ms 132920 KB Output is correct
8 Correct 170 ms 143224 KB Output is correct
9 Correct 169 ms 141820 KB Output is correct
10 Correct 170 ms 141540 KB Output is correct
11 Correct 67 ms 132052 KB Output is correct
12 Correct 166 ms 141608 KB Output is correct
13 Correct 198 ms 141744 KB Output is correct
14 Correct 190 ms 141816 KB Output is correct
15 Correct 160 ms 141888 KB Output is correct
16 Correct 167 ms 141116 KB Output is correct
17 Correct 151 ms 140612 KB Output is correct
18 Correct 163 ms 141544 KB Output is correct
19 Correct 99 ms 132936 KB Output is correct
20 Correct 198 ms 143192 KB Output is correct
21 Correct 176 ms 141772 KB Output is correct
22 Correct 157 ms 141596 KB Output is correct
23 Correct 67 ms 132048 KB Output is correct
24 Correct 173 ms 141520 KB Output is correct
25 Correct 160 ms 141776 KB Output is correct
26 Correct 169 ms 141840 KB Output is correct
27 Correct 160 ms 141956 KB Output is correct
28 Correct 171 ms 141148 KB Output is correct
29 Correct 155 ms 140580 KB Output is correct
30 Correct 164 ms 141412 KB Output is correct
31 Correct 2692 ms 189636 KB Output is correct
32 Correct 2586 ms 196160 KB Output is correct
33 Correct 2472 ms 191604 KB Output is correct
34 Correct 2107 ms 195644 KB Output is correct
35 Correct 2473 ms 183200 KB Output is correct
36 Correct 2432 ms 186808 KB Output is correct
37 Correct 2719 ms 194292 KB Output is correct
38 Correct 99 ms 132916 KB Output is correct
39 Correct 172 ms 143252 KB Output is correct
40 Correct 168 ms 141868 KB Output is correct
41 Correct 158 ms 141552 KB Output is correct
42 Correct 67 ms 132044 KB Output is correct
43 Correct 159 ms 141528 KB Output is correct
44 Correct 162 ms 141768 KB Output is correct
45 Correct 159 ms 141840 KB Output is correct
46 Correct 164 ms 142076 KB Output is correct
47 Correct 160 ms 141152 KB Output is correct
48 Correct 151 ms 140620 KB Output is correct
49 Correct 161 ms 141520 KB Output is correct
50 Correct 2601 ms 189868 KB Output is correct
51 Correct 2545 ms 196104 KB Output is correct
52 Correct 2437 ms 191668 KB Output is correct
53 Correct 2164 ms 195816 KB Output is correct
54 Correct 2480 ms 183324 KB Output is correct
55 Correct 2402 ms 186836 KB Output is correct
56 Correct 2659 ms 194208 KB Output is correct
57 Correct 2802 ms 237276 KB Output is correct
58 Correct 2761 ms 277080 KB Output is correct
59 Correct 2587 ms 238900 KB Output is correct
60 Correct 2135 ms 193684 KB Output is correct
61 Correct 2642 ms 234316 KB Output is correct
62 Correct 2571 ms 213924 KB Output is correct
63 Correct 68 ms 131792 KB Output is correct
64 Correct 68 ms 131840 KB Output is correct
65 Correct 66 ms 131812 KB Output is correct
66 Correct 100 ms 132968 KB Output is correct
67 Correct 169 ms 143180 KB Output is correct
68 Correct 170 ms 141864 KB Output is correct
69 Correct 157 ms 141548 KB Output is correct
70 Correct 68 ms 132060 KB Output is correct
71 Correct 156 ms 141600 KB Output is correct
72 Correct 166 ms 141768 KB Output is correct
73 Correct 162 ms 141844 KB Output is correct
74 Correct 165 ms 141948 KB Output is correct
75 Correct 161 ms 141196 KB Output is correct
76 Correct 159 ms 140588 KB Output is correct
77 Correct 169 ms 141504 KB Output is correct
78 Correct 2603 ms 186972 KB Output is correct
79 Correct 2682 ms 181752 KB Output is correct
80 Correct 2666 ms 183976 KB Output is correct
81 Incorrect 2436 ms 186840 KB Output isn't correct
82 Halted 0 ms 0 KB -