oj.uz

Submission #657491

# Submission time Handle Problem Language Result Execution time Memory
657491 2022-11-10T01:41:51 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 68732 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];
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++) {
        if(isrt[i]) {
            for(int j = 0; j < szrt[idrt[i]]; j++) {
                d[i].pb(inf);
            }
        }
        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(dist != d[u][t]) continue;

        if(isrt[u]) {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    int d1 = d[u][t]+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])) 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)));
                    }
                }
            }
        }
        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)));
                    }
                    // for(int i = 0; i < szrt[idrt[v]]; i++) {
                    //     int d1 = d[u][t]+1+i;
                    //     int t1 = d1%szrt[idrt[v]];
                    //     if(i != ((thrt[v]-d[u][t])%szrt[idrt[v]]+szrt[idrt[v]])%szrt[idrt[v]]) continue;
                    //     // if(t1 != (thrt[v]+1)%szrt[idrt[v]]) continue;
                    //     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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15320 KB Output is correct
2 Correct 104 ms 21424 KB Output is correct
3 Correct 107 ms 21048 KB Output is correct
4 Correct 142 ms 21168 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 114 ms 21012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15360 KB Output is correct
2 Correct 115 ms 21580 KB Output is correct
3 Correct 100 ms 21080 KB Output is correct
4 Correct 129 ms 21076 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 124 ms 21000 KB Output is correct
7 Correct 110 ms 20980 KB Output is correct
8 Correct 104 ms 20996 KB Output is correct
9 Correct 112 ms 20940 KB Output is correct
10 Correct 116 ms 21196 KB Output is correct
11 Correct 106 ms 21052 KB Output is correct
12 Correct 103 ms 20936 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15360 KB Output is correct
2 Correct 115 ms 21580 KB Output is correct
3 Correct 100 ms 21080 KB Output is correct
4 Correct 129 ms 21076 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 124 ms 21000 KB Output is correct
7 Correct 110 ms 20980 KB Output is correct
8 Correct 104 ms 20996 KB Output is correct
9 Correct 112 ms 20940 KB Output is correct
10 Correct 116 ms 21196 KB Output is correct
11 Correct 106 ms 21052 KB Output is correct
12 Correct 103 ms 20936 KB Output is correct
13 Correct 77 ms 15356 KB Output is correct
14 Correct 117 ms 21540 KB Output is correct
15 Correct 138 ms 21120 KB Output is correct
16 Correct 137 ms 21200 KB Output is correct
17 Correct 9 ms 14380 KB Output is correct
18 Correct 105 ms 20964 KB Output is correct
19 Correct 103 ms 20912 KB Output is correct
20 Correct 109 ms 21088 KB Output is correct
21 Correct 107 ms 20920 KB Output is correct
22 Correct 127 ms 21260 KB Output is correct
23 Correct 98 ms 21064 KB Output is correct
24 Correct 104 ms 21012 KB Output is correct
25 Correct 2640 ms 64012 KB Output is correct
26 Correct 2517 ms 68732 KB Output is correct
27 Correct 2360 ms 64744 KB Output is correct
28 Correct 2068 ms 68424 KB Output is correct
29 Execution timed out 6057 ms 59664 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15360 KB Output is correct
2 Correct 115 ms 21580 KB Output is correct
3 Correct 100 ms 21080 KB Output is correct
4 Correct 129 ms 21076 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 124 ms 21000 KB Output is correct
7 Correct 110 ms 20980 KB Output is correct
8 Correct 104 ms 20996 KB Output is correct
9 Correct 112 ms 20940 KB Output is correct
10 Correct 116 ms 21196 KB Output is correct
11 Correct 106 ms 21052 KB Output is correct
12 Correct 103 ms 20936 KB Output is correct
13 Correct 77 ms 15356 KB Output is correct
14 Correct 117 ms 21540 KB Output is correct
15 Correct 138 ms 21120 KB Output is correct
16 Correct 137 ms 21200 KB Output is correct
17 Correct 9 ms 14380 KB Output is correct
18 Correct 105 ms 20964 KB Output is correct
19 Correct 103 ms 20912 KB Output is correct
20 Correct 109 ms 21088 KB Output is correct
21 Correct 107 ms 20920 KB Output is correct
22 Correct 127 ms 21260 KB Output is correct
23 Correct 98 ms 21064 KB Output is correct
24 Correct 104 ms 21012 KB Output is correct
25 Correct 2640 ms 64012 KB Output is correct
26 Correct 2517 ms 68732 KB Output is correct
27 Correct 2360 ms 64744 KB Output is correct
28 Correct 2068 ms 68424 KB Output is correct
29 Execution timed out 6057 ms 59664 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15320 KB Output is correct
2 Correct 104 ms 21424 KB Output is correct
3 Correct 107 ms 21048 KB Output is correct
4 Correct 142 ms 21168 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 114 ms 21012 KB Output is correct
7 Correct 78 ms 15360 KB Output is correct
8 Correct 115 ms 21580 KB Output is correct
9 Correct 100 ms 21080 KB Output is correct
10 Correct 129 ms 21076 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 124 ms 21000 KB Output is correct
13 Correct 110 ms 20980 KB Output is correct
14 Correct 104 ms 20996 KB Output is correct
15 Correct 112 ms 20940 KB Output is correct
16 Correct 116 ms 21196 KB Output is correct
17 Correct 106 ms 21052 KB Output is correct
18 Correct 103 ms 20936 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 74 ms 15452 KB Output is correct
23 Correct 104 ms 21480 KB Output is correct
24 Correct 120 ms 21076 KB Output is correct
25 Correct 136 ms 21252 KB Output is correct
26 Correct 8 ms 14420 KB Output is correct
27 Correct 130 ms 21068 KB Output is correct
28 Correct 134 ms 20972 KB Output is correct
29 Correct 98 ms 21008 KB Output is correct
30 Correct 114 ms 20916 KB Output is correct
31 Correct 107 ms 21184 KB Output is correct
32 Correct 113 ms 21044 KB Output is correct
33 Correct 100 ms 21004 KB Output is correct
34 Correct 2554 ms 64452 KB Output is correct
35 Correct 2702 ms 60712 KB Output is correct
36 Correct 2675 ms 60968 KB Output is correct
37 Incorrect 2299 ms 65916 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15320 KB Output is correct
2 Correct 104 ms 21424 KB Output is correct
3 Correct 107 ms 21048 KB Output is correct
4 Correct 142 ms 21168 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 114 ms 21012 KB Output is correct
7 Correct 78 ms 15360 KB Output is correct
8 Correct 115 ms 21580 KB Output is correct
9 Correct 100 ms 21080 KB Output is correct
10 Correct 129 ms 21076 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 124 ms 21000 KB Output is correct
13 Correct 110 ms 20980 KB Output is correct
14 Correct 104 ms 20996 KB Output is correct
15 Correct 112 ms 20940 KB Output is correct
16 Correct 116 ms 21196 KB Output is correct
17 Correct 106 ms 21052 KB Output is correct
18 Correct 103 ms 20936 KB Output is correct
19 Correct 77 ms 15356 KB Output is correct
20 Correct 117 ms 21540 KB Output is correct
21 Correct 138 ms 21120 KB Output is correct
22 Correct 137 ms 21200 KB Output is correct
23 Correct 9 ms 14380 KB Output is correct
24 Correct 105 ms 20964 KB Output is correct
25 Correct 103 ms 20912 KB Output is correct
26 Correct 109 ms 21088 KB Output is correct
27 Correct 107 ms 20920 KB Output is correct
28 Correct 127 ms 21260 KB Output is correct
29 Correct 98 ms 21064 KB Output is correct
30 Correct 104 ms 21012 KB Output is correct
31 Correct 2640 ms 64012 KB Output is correct
32 Correct 2517 ms 68732 KB Output is correct
33 Correct 2360 ms 64744 KB Output is correct
34 Correct 2068 ms 68424 KB Output is correct
35 Execution timed out 6057 ms 59664 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15320 KB Output is correct
2 Correct 104 ms 21424 KB Output is correct
3 Correct 107 ms 21048 KB Output is correct
4 Correct 142 ms 21168 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 114 ms 21012 KB Output is correct
7 Correct 78 ms 15360 KB Output is correct
8 Correct 115 ms 21580 KB Output is correct
9 Correct 100 ms 21080 KB Output is correct
10 Correct 129 ms 21076 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 124 ms 21000 KB Output is correct
13 Correct 110 ms 20980 KB Output is correct
14 Correct 104 ms 20996 KB Output is correct
15 Correct 112 ms 20940 KB Output is correct
16 Correct 116 ms 21196 KB Output is correct
17 Correct 106 ms 21052 KB Output is correct
18 Correct 103 ms 20936 KB Output is correct
19 Correct 77 ms 15356 KB Output is correct
20 Correct 117 ms 21540 KB Output is correct
21 Correct 138 ms 21120 KB Output is correct
22 Correct 137 ms 21200 KB Output is correct
23 Correct 9 ms 14380 KB Output is correct
24 Correct 105 ms 20964 KB Output is correct
25 Correct 103 ms 20912 KB Output is correct
26 Correct 109 ms 21088 KB Output is correct
27 Correct 107 ms 20920 KB Output is correct
28 Correct 127 ms 21260 KB Output is correct
29 Correct 98 ms 21064 KB Output is correct
30 Correct 104 ms 21012 KB Output is correct
31 Correct 2640 ms 64012 KB Output is correct
32 Correct 2517 ms 68732 KB Output is correct
33 Correct 2360 ms 64744 KB Output is correct
34 Correct 2068 ms 68424 KB Output is correct
35 Execution timed out 6057 ms 59664 KB Time limit exceeded
36 Halted 0 ms 0 KB -