oj.uz

Submission #658713

# Submission time Handle Problem Language Result Execution time Memory
658713 2022-11-14T13:30:13 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
35 / 100
 3067 ms 269296 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];
pair<int,int> fqt1[maxn];
vector<int> g[maxn], gdiffrt[maxn], d[maxn];
vector<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;
                }

                if(isrt[v] && idrt[v] != idrt[u]) {
                    gdiffrt[u].pb(v);
                }
            }
        }
        else {
            d[i].pb(inf);
        }

    }

    d[1][0] = 0;
    withdist[0].pb(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.fr;
        int t = X.sc;
        if(t != -1 && distcur != d[u][t]) continue;
        if(t == -1 && distcur != 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(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(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(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(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(v,t1));
            }

            if(dlol[u] > d[u][t]) {
                dlol[u] = d[u][t];
                withdist[dlol[u]].pb(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(v,t1));
            }

            for(auto v : gdiffrt[u]) {
                d1 = d[u][t]+1;
                while(true) {
                    int t1 = d1%szrt[idrt[v]];
                    if(fqt1[t1] == mp(u,t)) break;
                    fqt1[t1] = mp(u,t);
                    // 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(v,t1));
                    }
                    d1+= szrt[idrt[u]];
                }
            }
        }
        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(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(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(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:86:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   86 |                     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 115 ms 140504 KB Output is correct
2 Correct 191 ms 151284 KB Output is correct
3 Correct 182 ms 149848 KB Output is correct
4 Correct 186 ms 149540 KB Output is correct
5 Correct 79 ms 139100 KB Output is correct
6 Correct 171 ms 149604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 140544 KB Output is correct
2 Correct 202 ms 151296 KB Output is correct
3 Correct 185 ms 149848 KB Output is correct
4 Correct 190 ms 149584 KB Output is correct
5 Correct 77 ms 139020 KB Output is correct
6 Correct 216 ms 149812 KB Output is correct
7 Correct 177 ms 149796 KB Output is correct
8 Correct 177 ms 150012 KB Output is correct
9 Correct 183 ms 150180 KB Output is correct
10 Correct 190 ms 148908 KB Output is correct
11 Correct 165 ms 148444 KB Output is correct
12 Correct 180 ms 149452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 140544 KB Output is correct
2 Correct 202 ms 151296 KB Output is correct
3 Correct 185 ms 149848 KB Output is correct
4 Correct 190 ms 149584 KB Output is correct
5 Correct 77 ms 139020 KB Output is correct
6 Correct 216 ms 149812 KB Output is correct
7 Correct 177 ms 149796 KB Output is correct
8 Correct 177 ms 150012 KB Output is correct
9 Correct 183 ms 150180 KB Output is correct
10 Correct 190 ms 148908 KB Output is correct
11 Correct 165 ms 148444 KB Output is correct
12 Correct 180 ms 149452 KB Output is correct
13 Correct 119 ms 140460 KB Output is correct
14 Correct 180 ms 151304 KB Output is correct
15 Correct 169 ms 149764 KB Output is correct
16 Correct 185 ms 149496 KB Output is correct
17 Correct 94 ms 139040 KB Output is correct
18 Correct 171 ms 149600 KB Output is correct
19 Correct 183 ms 149828 KB Output is correct
20 Correct 183 ms 150068 KB Output is correct
21 Correct 198 ms 150220 KB Output is correct
22 Correct 181 ms 148900 KB Output is correct
23 Correct 194 ms 148432 KB Output is correct
24 Correct 173 ms 149452 KB Output is correct
25 Correct 2853 ms 201044 KB Output is correct
26 Correct 2716 ms 207748 KB Output is correct
27 Correct 2589 ms 203376 KB Output is correct
28 Correct 2293 ms 207776 KB Output is correct
29 Correct 2645 ms 194840 KB Output is correct
30 Correct 2593 ms 199232 KB Output is correct
31 Correct 2975 ms 207636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 140544 KB Output is correct
2 Correct 202 ms 151296 KB Output is correct
3 Correct 185 ms 149848 KB Output is correct
4 Correct 190 ms 149584 KB Output is correct
5 Correct 77 ms 139020 KB Output is correct
6 Correct 216 ms 149812 KB Output is correct
7 Correct 177 ms 149796 KB Output is correct
8 Correct 177 ms 150012 KB Output is correct
9 Correct 183 ms 150180 KB Output is correct
10 Correct 190 ms 148908 KB Output is correct
11 Correct 165 ms 148444 KB Output is correct
12 Correct 180 ms 149452 KB Output is correct
13 Correct 119 ms 140460 KB Output is correct
14 Correct 180 ms 151304 KB Output is correct
15 Correct 169 ms 149764 KB Output is correct
16 Correct 185 ms 149496 KB Output is correct
17 Correct 94 ms 139040 KB Output is correct
18 Correct 171 ms 149600 KB Output is correct
19 Correct 183 ms 149828 KB Output is correct
20 Correct 183 ms 150068 KB Output is correct
21 Correct 198 ms 150220 KB Output is correct
22 Correct 181 ms 148900 KB Output is correct
23 Correct 194 ms 148432 KB Output is correct
24 Correct 173 ms 149452 KB Output is correct
25 Correct 2853 ms 201044 KB Output is correct
26 Correct 2716 ms 207748 KB Output is correct
27 Correct 2589 ms 203376 KB Output is correct
28 Correct 2293 ms 207776 KB Output is correct
29 Correct 2645 ms 194840 KB Output is correct
30 Correct 2593 ms 199232 KB Output is correct
31 Correct 2975 ms 207636 KB Output is correct
32 Correct 120 ms 140544 KB Output is correct
33 Correct 199 ms 151392 KB Output is correct
34 Correct 192 ms 149836 KB Output is correct
35 Correct 192 ms 149472 KB Output is correct
36 Correct 81 ms 138992 KB Output is correct
37 Correct 177 ms 149744 KB Output is correct
38 Correct 182 ms 149960 KB Output is correct
39 Correct 189 ms 149940 KB Output is correct
40 Correct 178 ms 150228 KB Output is correct
41 Correct 185 ms 148880 KB Output is correct
42 Correct 200 ms 148368 KB Output is correct
43 Correct 177 ms 149484 KB Output is correct
44 Correct 2855 ms 199580 KB Output is correct
45 Correct 2991 ms 205092 KB Output is correct
46 Correct 2815 ms 199536 KB Output is correct
47 Correct 2619 ms 209884 KB Output is correct
48 Correct 2658 ms 191076 KB Output is correct
49 Correct 2609 ms 195996 KB Output is correct
50 Correct 2925 ms 203900 KB Output is correct
51 Correct 3067 ms 236876 KB Output is correct
52 Correct 3065 ms 269296 KB Output is correct
53 Correct 2892 ms 236312 KB Output is correct
54 Correct 2278 ms 210948 KB Output is correct
55 Correct 2828 ms 234500 KB Output is correct
56 Correct 2829 ms 215172 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 140504 KB Output is correct
2 Correct 191 ms 151284 KB Output is correct
3 Correct 182 ms 149848 KB Output is correct
4 Correct 186 ms 149540 KB Output is correct
5 Correct 79 ms 139100 KB Output is correct
6 Correct 171 ms 149604 KB Output is correct
7 Correct 113 ms 140544 KB Output is correct
8 Correct 202 ms 151296 KB Output is correct
9 Correct 185 ms 149848 KB Output is correct
10 Correct 190 ms 149584 KB Output is correct
11 Correct 77 ms 139020 KB Output is correct
12 Correct 216 ms 149812 KB Output is correct
13 Correct 177 ms 149796 KB Output is correct
14 Correct 177 ms 150012 KB Output is correct
15 Correct 183 ms 150180 KB Output is correct
16 Correct 190 ms 148908 KB Output is correct
17 Correct 165 ms 148444 KB Output is correct
18 Correct 180 ms 149452 KB Output is correct
19 Correct 81 ms 138884 KB Output is correct
20 Correct 80 ms 138824 KB Output is correct
21 Correct 85 ms 138768 KB Output is correct
22 Correct 120 ms 140456 KB Output is correct
23 Correct 214 ms 151528 KB Output is correct
24 Correct 177 ms 149836 KB Output is correct
25 Correct 192 ms 149540 KB Output is correct
26 Correct 88 ms 139104 KB Output is correct
27 Correct 177 ms 149584 KB Output is correct
28 Correct 178 ms 149788 KB Output is correct
29 Correct 181 ms 149964 KB Output is correct
30 Correct 203 ms 150236 KB Output is correct
31 Correct 186 ms 148924 KB Output is correct
32 Correct 172 ms 148372 KB Output is correct
33 Correct 173 ms 149568 KB Output is correct
34 Correct 2777 ms 194248 KB Output is correct
35 Correct 2891 ms 195104 KB Output is correct
36 Correct 2903 ms 191816 KB Output is correct
37 Incorrect 2545 ms 194588 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 140504 KB Output is correct
2 Correct 191 ms 151284 KB Output is correct
3 Correct 182 ms 149848 KB Output is correct
4 Correct 186 ms 149540 KB Output is correct
5 Correct 79 ms 139100 KB Output is correct
6 Correct 171 ms 149604 KB Output is correct
7 Correct 113 ms 140544 KB Output is correct
8 Correct 202 ms 151296 KB Output is correct
9 Correct 185 ms 149848 KB Output is correct
10 Correct 190 ms 149584 KB Output is correct
11 Correct 77 ms 139020 KB Output is correct
12 Correct 216 ms 149812 KB Output is correct
13 Correct 177 ms 149796 KB Output is correct
14 Correct 177 ms 150012 KB Output is correct
15 Correct 183 ms 150180 KB Output is correct
16 Correct 190 ms 148908 KB Output is correct
17 Correct 165 ms 148444 KB Output is correct
18 Correct 180 ms 149452 KB Output is correct
19 Correct 119 ms 140460 KB Output is correct
20 Correct 180 ms 151304 KB Output is correct
21 Correct 169 ms 149764 KB Output is correct
22 Correct 185 ms 149496 KB Output is correct
23 Correct 94 ms 139040 KB Output is correct
24 Correct 171 ms 149600 KB Output is correct
25 Correct 183 ms 149828 KB Output is correct
26 Correct 183 ms 150068 KB Output is correct
27 Correct 198 ms 150220 KB Output is correct
28 Correct 181 ms 148900 KB Output is correct
29 Correct 194 ms 148432 KB Output is correct
30 Correct 173 ms 149452 KB Output is correct
31 Correct 2853 ms 201044 KB Output is correct
32 Correct 2716 ms 207748 KB Output is correct
33 Correct 2589 ms 203376 KB Output is correct
34 Correct 2293 ms 207776 KB Output is correct
35 Correct 2645 ms 194840 KB Output is correct
36 Correct 2593 ms 199232 KB Output is correct
37 Correct 2975 ms 207636 KB Output is correct
38 Correct 81 ms 138884 KB Output is correct
39 Correct 80 ms 138824 KB Output is correct
40 Correct 85 ms 138768 KB Output is correct
41 Correct 120 ms 140456 KB Output is correct
42 Correct 214 ms 151528 KB Output is correct
43 Correct 177 ms 149836 KB Output is correct
44 Correct 192 ms 149540 KB Output is correct
45 Correct 88 ms 139104 KB Output is correct
46 Correct 177 ms 149584 KB Output is correct
47 Correct 178 ms 149788 KB Output is correct
48 Correct 181 ms 149964 KB Output is correct
49 Correct 203 ms 150236 KB Output is correct
50 Correct 186 ms 148924 KB Output is correct
51 Correct 172 ms 148372 KB Output is correct
52 Correct 173 ms 149568 KB Output is correct
53 Correct 2777 ms 194248 KB Output is correct
54 Correct 2891 ms 195104 KB Output is correct
55 Correct 2903 ms 191816 KB Output is correct
56 Incorrect 2545 ms 194588 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 140504 KB Output is correct
2 Correct 191 ms 151284 KB Output is correct
3 Correct 182 ms 149848 KB Output is correct
4 Correct 186 ms 149540 KB Output is correct
5 Correct 79 ms 139100 KB Output is correct
6 Correct 171 ms 149604 KB Output is correct
7 Correct 113 ms 140544 KB Output is correct
8 Correct 202 ms 151296 KB Output is correct
9 Correct 185 ms 149848 KB Output is correct
10 Correct 190 ms 149584 KB Output is correct
11 Correct 77 ms 139020 KB Output is correct
12 Correct 216 ms 149812 KB Output is correct
13 Correct 177 ms 149796 KB Output is correct
14 Correct 177 ms 150012 KB Output is correct
15 Correct 183 ms 150180 KB Output is correct
16 Correct 190 ms 148908 KB Output is correct
17 Correct 165 ms 148444 KB Output is correct
18 Correct 180 ms 149452 KB Output is correct
19 Correct 119 ms 140460 KB Output is correct
20 Correct 180 ms 151304 KB Output is correct
21 Correct 169 ms 149764 KB Output is correct
22 Correct 185 ms 149496 KB Output is correct
23 Correct 94 ms 139040 KB Output is correct
24 Correct 171 ms 149600 KB Output is correct
25 Correct 183 ms 149828 KB Output is correct
26 Correct 183 ms 150068 KB Output is correct
27 Correct 198 ms 150220 KB Output is correct
28 Correct 181 ms 148900 KB Output is correct
29 Correct 194 ms 148432 KB Output is correct
30 Correct 173 ms 149452 KB Output is correct
31 Correct 2853 ms 201044 KB Output is correct
32 Correct 2716 ms 207748 KB Output is correct
33 Correct 2589 ms 203376 KB Output is correct
34 Correct 2293 ms 207776 KB Output is correct
35 Correct 2645 ms 194840 KB Output is correct
36 Correct 2593 ms 199232 KB Output is correct
37 Correct 2975 ms 207636 KB Output is correct
38 Correct 120 ms 140544 KB Output is correct
39 Correct 199 ms 151392 KB Output is correct
40 Correct 192 ms 149836 KB Output is correct
41 Correct 192 ms 149472 KB Output is correct
42 Correct 81 ms 138992 KB Output is correct
43 Correct 177 ms 149744 KB Output is correct
44 Correct 182 ms 149960 KB Output is correct
45 Correct 189 ms 149940 KB Output is correct
46 Correct 178 ms 150228 KB Output is correct
47 Correct 185 ms 148880 KB Output is correct
48 Correct 200 ms 148368 KB Output is correct
49 Correct 177 ms 149484 KB Output is correct
50 Correct 2855 ms 199580 KB Output is correct
51 Correct 2991 ms 205092 KB Output is correct
52 Correct 2815 ms 199536 KB Output is correct
53 Correct 2619 ms 209884 KB Output is correct
54 Correct 2658 ms 191076 KB Output is correct
55 Correct 2609 ms 195996 KB Output is correct
56 Correct 2925 ms 203900 KB Output is correct
57 Correct 3067 ms 236876 KB Output is correct
58 Correct 3065 ms 269296 KB Output is correct
59 Correct 2892 ms 236312 KB Output is correct
60 Correct 2278 ms 210948 KB Output is correct
61 Correct 2828 ms 234500 KB Output is correct
62 Correct 2829 ms 215172 KB Output is correct
63 Correct 81 ms 138884 KB Output is correct
64 Correct 80 ms 138824 KB Output is correct
65 Correct 85 ms 138768 KB Output is correct
66 Correct 120 ms 140456 KB Output is correct
67 Correct 214 ms 151528 KB Output is correct
68 Correct 177 ms 149836 KB Output is correct
69 Correct 192 ms 149540 KB Output is correct
70 Correct 88 ms 139104 KB Output is correct
71 Correct 177 ms 149584 KB Output is correct
72 Correct 178 ms 149788 KB Output is correct
73 Correct 181 ms 149964 KB Output is correct
74 Correct 203 ms 150236 KB Output is correct
75 Correct 186 ms 148924 KB Output is correct
76 Correct 172 ms 148372 KB Output is correct
77 Correct 173 ms 149568 KB Output is correct
78 Correct 2777 ms 194248 KB Output is correct
79 Correct 2891 ms 195104 KB Output is correct
80 Correct 2903 ms 191816 KB Output is correct
81 Incorrect 2545 ms 194588 KB Output isn't correct
82 Halted 0 ms 0 KB -