oj.uz

Submission #658708

# Submission time Handle Problem Language Result Execution time Memory
658708 2022-11-14T13:13:14 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
35 / 100
 3193 ms 441848 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 = 1e7;

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;
    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)));
    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;
    // 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)));
                        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;
                                pq.push(mp(d[v][t1],mp(v,t1)));
                                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;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        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;
                pq.push(mp(d[v][t1],mp(v,t1)));
                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;
                pq.push(mp(d[v][t1],mp(v,t1)));
                withdist[d[v][t1]].pb(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)));
                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;
                pq.push(mp(d[v][t1],mp(v,t1)));
                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;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        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;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        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;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        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:90:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |                     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 192 ms 250816 KB Output is correct
2 Correct 271 ms 262364 KB Output is correct
3 Correct 263 ms 260876 KB Output is correct
4 Correct 275 ms 260728 KB Output is correct
5 Correct 152 ms 249612 KB Output is correct
6 Correct 288 ms 260592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 250936 KB Output is correct
2 Correct 286 ms 262332 KB Output is correct
3 Correct 289 ms 260832 KB Output is correct
4 Correct 277 ms 260696 KB Output is correct
5 Correct 163 ms 249704 KB Output is correct
6 Correct 260 ms 260596 KB Output is correct
7 Correct 260 ms 260736 KB Output is correct
8 Correct 288 ms 260772 KB Output is correct
9 Correct 291 ms 260924 KB Output is correct
10 Correct 256 ms 260044 KB Output is correct
11 Correct 253 ms 259460 KB Output is correct
12 Correct 275 ms 260452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 250936 KB Output is correct
2 Correct 286 ms 262332 KB Output is correct
3 Correct 289 ms 260832 KB Output is correct
4 Correct 277 ms 260696 KB Output is correct
5 Correct 163 ms 249704 KB Output is correct
6 Correct 260 ms 260596 KB Output is correct
7 Correct 260 ms 260736 KB Output is correct
8 Correct 288 ms 260772 KB Output is correct
9 Correct 291 ms 260924 KB Output is correct
10 Correct 256 ms 260044 KB Output is correct
11 Correct 253 ms 259460 KB Output is correct
12 Correct 275 ms 260452 KB Output is correct
13 Correct 191 ms 250996 KB Output is correct
14 Correct 327 ms 262364 KB Output is correct
15 Correct 255 ms 260860 KB Output is correct
16 Correct 308 ms 260736 KB Output is correct
17 Correct 151 ms 249716 KB Output is correct
18 Correct 259 ms 260612 KB Output is correct
19 Correct 282 ms 260736 KB Output is correct
20 Correct 257 ms 260788 KB Output is correct
21 Correct 283 ms 260964 KB Output is correct
22 Correct 264 ms 260096 KB Output is correct
23 Correct 279 ms 259552 KB Output is correct
24 Correct 276 ms 260340 KB Output is correct
25 Correct 2997 ms 312988 KB Output is correct
26 Correct 2882 ms 318920 KB Output is correct
27 Correct 2889 ms 314836 KB Output is correct
28 Correct 2436 ms 316532 KB Output is correct
29 Correct 2647 ms 306484 KB Output is correct
30 Correct 2716 ms 309652 KB Output is correct
31 Correct 2964 ms 317568 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 250936 KB Output is correct
2 Correct 286 ms 262332 KB Output is correct
3 Correct 289 ms 260832 KB Output is correct
4 Correct 277 ms 260696 KB Output is correct
5 Correct 163 ms 249704 KB Output is correct
6 Correct 260 ms 260596 KB Output is correct
7 Correct 260 ms 260736 KB Output is correct
8 Correct 288 ms 260772 KB Output is correct
9 Correct 291 ms 260924 KB Output is correct
10 Correct 256 ms 260044 KB Output is correct
11 Correct 253 ms 259460 KB Output is correct
12 Correct 275 ms 260452 KB Output is correct
13 Correct 191 ms 250996 KB Output is correct
14 Correct 327 ms 262364 KB Output is correct
15 Correct 255 ms 260860 KB Output is correct
16 Correct 308 ms 260736 KB Output is correct
17 Correct 151 ms 249716 KB Output is correct
18 Correct 259 ms 260612 KB Output is correct
19 Correct 282 ms 260736 KB Output is correct
20 Correct 257 ms 260788 KB Output is correct
21 Correct 283 ms 260964 KB Output is correct
22 Correct 264 ms 260096 KB Output is correct
23 Correct 279 ms 259552 KB Output is correct
24 Correct 276 ms 260340 KB Output is correct
25 Correct 2997 ms 312988 KB Output is correct
26 Correct 2882 ms 318920 KB Output is correct
27 Correct 2889 ms 314836 KB Output is correct
28 Correct 2436 ms 316532 KB Output is correct
29 Correct 2647 ms 306484 KB Output is correct
30 Correct 2716 ms 309652 KB Output is correct
31 Correct 2964 ms 317568 KB Output is correct
32 Correct 180 ms 250932 KB Output is correct
33 Correct 290 ms 262368 KB Output is correct
34 Correct 275 ms 260972 KB Output is correct
35 Correct 272 ms 260696 KB Output is correct
36 Correct 163 ms 249672 KB Output is correct
37 Correct 264 ms 260640 KB Output is correct
38 Correct 286 ms 260724 KB Output is correct
39 Correct 276 ms 260744 KB Output is correct
40 Correct 274 ms 260980 KB Output is correct
41 Correct 261 ms 260212 KB Output is correct
42 Correct 261 ms 259536 KB Output is correct
43 Correct 265 ms 260472 KB Output is correct
44 Correct 2943 ms 312944 KB Output is correct
45 Correct 2864 ms 319008 KB Output is correct
46 Correct 2734 ms 314672 KB Output is correct
47 Correct 2440 ms 316944 KB Output is correct
48 Correct 2678 ms 306464 KB Output is correct
49 Correct 2607 ms 309460 KB Output is correct
50 Correct 2903 ms 317300 KB Output is correct
51 Correct 3063 ms 397008 KB Output is correct
52 Correct 3158 ms 441848 KB Output is correct
53 Correct 2970 ms 395964 KB Output is correct
54 Correct 2345 ms 324356 KB Output is correct
55 Correct 2967 ms 393612 KB Output is correct
56 Correct 2880 ms 355768 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 250816 KB Output is correct
2 Correct 271 ms 262364 KB Output is correct
3 Correct 263 ms 260876 KB Output is correct
4 Correct 275 ms 260728 KB Output is correct
5 Correct 152 ms 249612 KB Output is correct
6 Correct 288 ms 260592 KB Output is correct
7 Correct 216 ms 250936 KB Output is correct
8 Correct 286 ms 262332 KB Output is correct
9 Correct 289 ms 260832 KB Output is correct
10 Correct 277 ms 260696 KB Output is correct
11 Correct 163 ms 249704 KB Output is correct
12 Correct 260 ms 260596 KB Output is correct
13 Correct 260 ms 260736 KB Output is correct
14 Correct 288 ms 260772 KB Output is correct
15 Correct 291 ms 260924 KB Output is correct
16 Correct 256 ms 260044 KB Output is correct
17 Correct 253 ms 259460 KB Output is correct
18 Correct 275 ms 260452 KB Output is correct
19 Correct 141 ms 249292 KB Output is correct
20 Correct 138 ms 249252 KB Output is correct
21 Correct 141 ms 249244 KB Output is correct
22 Correct 171 ms 250904 KB Output is correct
23 Correct 288 ms 262360 KB Output is correct
24 Correct 253 ms 260864 KB Output is correct
25 Correct 257 ms 260672 KB Output is correct
26 Correct 139 ms 249680 KB Output is correct
27 Correct 238 ms 260688 KB Output is correct
28 Correct 255 ms 260736 KB Output is correct
29 Correct 240 ms 260764 KB Output is correct
30 Correct 238 ms 260860 KB Output is correct
31 Correct 248 ms 260104 KB Output is correct
32 Correct 236 ms 259708 KB Output is correct
33 Correct 244 ms 260372 KB Output is correct
34 Correct 2870 ms 307404 KB Output is correct
35 Correct 2800 ms 303092 KB Output is correct
36 Correct 2854 ms 304728 KB Output is correct
37 Incorrect 3193 ms 306572 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 250816 KB Output is correct
2 Correct 271 ms 262364 KB Output is correct
3 Correct 263 ms 260876 KB Output is correct
4 Correct 275 ms 260728 KB Output is correct
5 Correct 152 ms 249612 KB Output is correct
6 Correct 288 ms 260592 KB Output is correct
7 Correct 216 ms 250936 KB Output is correct
8 Correct 286 ms 262332 KB Output is correct
9 Correct 289 ms 260832 KB Output is correct
10 Correct 277 ms 260696 KB Output is correct
11 Correct 163 ms 249704 KB Output is correct
12 Correct 260 ms 260596 KB Output is correct
13 Correct 260 ms 260736 KB Output is correct
14 Correct 288 ms 260772 KB Output is correct
15 Correct 291 ms 260924 KB Output is correct
16 Correct 256 ms 260044 KB Output is correct
17 Correct 253 ms 259460 KB Output is correct
18 Correct 275 ms 260452 KB Output is correct
19 Correct 191 ms 250996 KB Output is correct
20 Correct 327 ms 262364 KB Output is correct
21 Correct 255 ms 260860 KB Output is correct
22 Correct 308 ms 260736 KB Output is correct
23 Correct 151 ms 249716 KB Output is correct
24 Correct 259 ms 260612 KB Output is correct
25 Correct 282 ms 260736 KB Output is correct
26 Correct 257 ms 260788 KB Output is correct
27 Correct 283 ms 260964 KB Output is correct
28 Correct 264 ms 260096 KB Output is correct
29 Correct 279 ms 259552 KB Output is correct
30 Correct 276 ms 260340 KB Output is correct
31 Correct 2997 ms 312988 KB Output is correct
32 Correct 2882 ms 318920 KB Output is correct
33 Correct 2889 ms 314836 KB Output is correct
34 Correct 2436 ms 316532 KB Output is correct
35 Correct 2647 ms 306484 KB Output is correct
36 Correct 2716 ms 309652 KB Output is correct
37 Correct 2964 ms 317568 KB Output is correct
38 Correct 141 ms 249292 KB Output is correct
39 Correct 138 ms 249252 KB Output is correct
40 Correct 141 ms 249244 KB Output is correct
41 Correct 171 ms 250904 KB Output is correct
42 Correct 288 ms 262360 KB Output is correct
43 Correct 253 ms 260864 KB Output is correct
44 Correct 257 ms 260672 KB Output is correct
45 Correct 139 ms 249680 KB Output is correct
46 Correct 238 ms 260688 KB Output is correct
47 Correct 255 ms 260736 KB Output is correct
48 Correct 240 ms 260764 KB Output is correct
49 Correct 238 ms 260860 KB Output is correct
50 Correct 248 ms 260104 KB Output is correct
51 Correct 236 ms 259708 KB Output is correct
52 Correct 244 ms 260372 KB Output is correct
53 Correct 2870 ms 307404 KB Output is correct
54 Correct 2800 ms 303092 KB Output is correct
55 Correct 2854 ms 304728 KB Output is correct
56 Incorrect 3193 ms 306572 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 250816 KB Output is correct
2 Correct 271 ms 262364 KB Output is correct
3 Correct 263 ms 260876 KB Output is correct
4 Correct 275 ms 260728 KB Output is correct
5 Correct 152 ms 249612 KB Output is correct
6 Correct 288 ms 260592 KB Output is correct
7 Correct 216 ms 250936 KB Output is correct
8 Correct 286 ms 262332 KB Output is correct
9 Correct 289 ms 260832 KB Output is correct
10 Correct 277 ms 260696 KB Output is correct
11 Correct 163 ms 249704 KB Output is correct
12 Correct 260 ms 260596 KB Output is correct
13 Correct 260 ms 260736 KB Output is correct
14 Correct 288 ms 260772 KB Output is correct
15 Correct 291 ms 260924 KB Output is correct
16 Correct 256 ms 260044 KB Output is correct
17 Correct 253 ms 259460 KB Output is correct
18 Correct 275 ms 260452 KB Output is correct
19 Correct 191 ms 250996 KB Output is correct
20 Correct 327 ms 262364 KB Output is correct
21 Correct 255 ms 260860 KB Output is correct
22 Correct 308 ms 260736 KB Output is correct
23 Correct 151 ms 249716 KB Output is correct
24 Correct 259 ms 260612 KB Output is correct
25 Correct 282 ms 260736 KB Output is correct
26 Correct 257 ms 260788 KB Output is correct
27 Correct 283 ms 260964 KB Output is correct
28 Correct 264 ms 260096 KB Output is correct
29 Correct 279 ms 259552 KB Output is correct
30 Correct 276 ms 260340 KB Output is correct
31 Correct 2997 ms 312988 KB Output is correct
32 Correct 2882 ms 318920 KB Output is correct
33 Correct 2889 ms 314836 KB Output is correct
34 Correct 2436 ms 316532 KB Output is correct
35 Correct 2647 ms 306484 KB Output is correct
36 Correct 2716 ms 309652 KB Output is correct
37 Correct 2964 ms 317568 KB Output is correct
38 Correct 180 ms 250932 KB Output is correct
39 Correct 290 ms 262368 KB Output is correct
40 Correct 275 ms 260972 KB Output is correct
41 Correct 272 ms 260696 KB Output is correct
42 Correct 163 ms 249672 KB Output is correct
43 Correct 264 ms 260640 KB Output is correct
44 Correct 286 ms 260724 KB Output is correct
45 Correct 276 ms 260744 KB Output is correct
46 Correct 274 ms 260980 KB Output is correct
47 Correct 261 ms 260212 KB Output is correct
48 Correct 261 ms 259536 KB Output is correct
49 Correct 265 ms 260472 KB Output is correct
50 Correct 2943 ms 312944 KB Output is correct
51 Correct 2864 ms 319008 KB Output is correct
52 Correct 2734 ms 314672 KB Output is correct
53 Correct 2440 ms 316944 KB Output is correct
54 Correct 2678 ms 306464 KB Output is correct
55 Correct 2607 ms 309460 KB Output is correct
56 Correct 2903 ms 317300 KB Output is correct
57 Correct 3063 ms 397008 KB Output is correct
58 Correct 3158 ms 441848 KB Output is correct
59 Correct 2970 ms 395964 KB Output is correct
60 Correct 2345 ms 324356 KB Output is correct
61 Correct 2967 ms 393612 KB Output is correct
62 Correct 2880 ms 355768 KB Output is correct
63 Correct 141 ms 249292 KB Output is correct
64 Correct 138 ms 249252 KB Output is correct
65 Correct 141 ms 249244 KB Output is correct
66 Correct 171 ms 250904 KB Output is correct
67 Correct 288 ms 262360 KB Output is correct
68 Correct 253 ms 260864 KB Output is correct
69 Correct 257 ms 260672 KB Output is correct
70 Correct 139 ms 249680 KB Output is correct
71 Correct 238 ms 260688 KB Output is correct
72 Correct 255 ms 260736 KB Output is correct
73 Correct 240 ms 260764 KB Output is correct
74 Correct 238 ms 260860 KB Output is correct
75 Correct 248 ms 260104 KB Output is correct
76 Correct 236 ms 259708 KB Output is correct
77 Correct 244 ms 260372 KB Output is correct
78 Correct 2870 ms 307404 KB Output is correct
79 Correct 2800 ms 303092 KB Output is correct
80 Correct 2854 ms 304728 KB Output is correct
81 Incorrect 3193 ms 306572 KB Output isn't correct
82 Halted 0 ms 0 KB -