oj.uz

Submission #657489

# Submission time Handle Problem Language Result Execution time Memory
657489 2022-11-10T01:40:18 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 109584 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 75 ms 16276 KB Output is correct
2 Correct 113 ms 21944 KB Output is correct
3 Correct 108 ms 21784 KB Output is correct
4 Correct 143 ms 21928 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 134 ms 21756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16256 KB Output is correct
2 Correct 121 ms 21860 KB Output is correct
3 Correct 140 ms 21764 KB Output is correct
4 Correct 135 ms 21744 KB Output is correct
5 Correct 12 ms 14548 KB Output is correct
6 Correct 115 ms 21712 KB Output is correct
7 Correct 108 ms 21580 KB Output is correct
8 Correct 125 ms 21668 KB Output is correct
9 Correct 104 ms 21588 KB Output is correct
10 Correct 116 ms 21832 KB Output is correct
11 Correct 120 ms 21676 KB Output is correct
12 Correct 120 ms 21656 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16256 KB Output is correct
2 Correct 121 ms 21860 KB Output is correct
3 Correct 140 ms 21764 KB Output is correct
4 Correct 135 ms 21744 KB Output is correct
5 Correct 12 ms 14548 KB Output is correct
6 Correct 115 ms 21712 KB Output is correct
7 Correct 108 ms 21580 KB Output is correct
8 Correct 125 ms 21668 KB Output is correct
9 Correct 104 ms 21588 KB Output is correct
10 Correct 116 ms 21832 KB Output is correct
11 Correct 120 ms 21676 KB Output is correct
12 Correct 120 ms 21656 KB Output is correct
13 Correct 73 ms 16280 KB Output is correct
14 Correct 143 ms 21772 KB Output is correct
15 Correct 121 ms 21716 KB Output is correct
16 Correct 139 ms 21788 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 124 ms 21828 KB Output is correct
19 Correct 119 ms 21608 KB Output is correct
20 Correct 109 ms 21644 KB Output is correct
21 Correct 103 ms 21716 KB Output is correct
22 Correct 110 ms 21840 KB Output is correct
23 Correct 133 ms 21644 KB Output is correct
24 Correct 118 ms 21684 KB Output is correct
25 Correct 2677 ms 97144 KB Output is correct
26 Correct 2634 ms 109584 KB Output is correct
27 Correct 2579 ms 96972 KB Output is correct
28 Correct 2191 ms 106644 KB Output is correct
29 Execution timed out 6047 ms 88460 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16256 KB Output is correct
2 Correct 121 ms 21860 KB Output is correct
3 Correct 140 ms 21764 KB Output is correct
4 Correct 135 ms 21744 KB Output is correct
5 Correct 12 ms 14548 KB Output is correct
6 Correct 115 ms 21712 KB Output is correct
7 Correct 108 ms 21580 KB Output is correct
8 Correct 125 ms 21668 KB Output is correct
9 Correct 104 ms 21588 KB Output is correct
10 Correct 116 ms 21832 KB Output is correct
11 Correct 120 ms 21676 KB Output is correct
12 Correct 120 ms 21656 KB Output is correct
13 Correct 73 ms 16280 KB Output is correct
14 Correct 143 ms 21772 KB Output is correct
15 Correct 121 ms 21716 KB Output is correct
16 Correct 139 ms 21788 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 124 ms 21828 KB Output is correct
19 Correct 119 ms 21608 KB Output is correct
20 Correct 109 ms 21644 KB Output is correct
21 Correct 103 ms 21716 KB Output is correct
22 Correct 110 ms 21840 KB Output is correct
23 Correct 133 ms 21644 KB Output is correct
24 Correct 118 ms 21684 KB Output is correct
25 Correct 2677 ms 97144 KB Output is correct
26 Correct 2634 ms 109584 KB Output is correct
27 Correct 2579 ms 96972 KB Output is correct
28 Correct 2191 ms 106644 KB Output is correct
29 Execution timed out 6047 ms 88460 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 16276 KB Output is correct
2 Correct 113 ms 21944 KB Output is correct
3 Correct 108 ms 21784 KB Output is correct
4 Correct 143 ms 21928 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 134 ms 21756 KB Output is correct
7 Correct 72 ms 16256 KB Output is correct
8 Correct 121 ms 21860 KB Output is correct
9 Correct 140 ms 21764 KB Output is correct
10 Correct 135 ms 21744 KB Output is correct
11 Correct 12 ms 14548 KB Output is correct
12 Correct 115 ms 21712 KB Output is correct
13 Correct 108 ms 21580 KB Output is correct
14 Correct 125 ms 21668 KB Output is correct
15 Correct 104 ms 21588 KB Output is correct
16 Correct 116 ms 21832 KB Output is correct
17 Correct 120 ms 21676 KB Output is correct
18 Correct 120 ms 21656 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 73 ms 16160 KB Output is correct
23 Correct 123 ms 21832 KB Output is correct
24 Correct 99 ms 21708 KB Output is correct
25 Correct 134 ms 21812 KB Output is correct
26 Correct 9 ms 14548 KB Output is correct
27 Correct 146 ms 21756 KB Output is correct
28 Correct 103 ms 21636 KB Output is correct
29 Correct 111 ms 21580 KB Output is correct
30 Correct 100 ms 21556 KB Output is correct
31 Correct 128 ms 21844 KB Output is correct
32 Correct 125 ms 21800 KB Output is correct
33 Correct 113 ms 21680 KB Output is correct
34 Correct 2772 ms 98556 KB Output is correct
35 Correct 2664 ms 91692 KB Output is correct
36 Correct 2722 ms 91624 KB Output is correct
37 Incorrect 2482 ms 104104 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 16276 KB Output is correct
2 Correct 113 ms 21944 KB Output is correct
3 Correct 108 ms 21784 KB Output is correct
4 Correct 143 ms 21928 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 134 ms 21756 KB Output is correct
7 Correct 72 ms 16256 KB Output is correct
8 Correct 121 ms 21860 KB Output is correct
9 Correct 140 ms 21764 KB Output is correct
10 Correct 135 ms 21744 KB Output is correct
11 Correct 12 ms 14548 KB Output is correct
12 Correct 115 ms 21712 KB Output is correct
13 Correct 108 ms 21580 KB Output is correct
14 Correct 125 ms 21668 KB Output is correct
15 Correct 104 ms 21588 KB Output is correct
16 Correct 116 ms 21832 KB Output is correct
17 Correct 120 ms 21676 KB Output is correct
18 Correct 120 ms 21656 KB Output is correct
19 Correct 73 ms 16280 KB Output is correct
20 Correct 143 ms 21772 KB Output is correct
21 Correct 121 ms 21716 KB Output is correct
22 Correct 139 ms 21788 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 124 ms 21828 KB Output is correct
25 Correct 119 ms 21608 KB Output is correct
26 Correct 109 ms 21644 KB Output is correct
27 Correct 103 ms 21716 KB Output is correct
28 Correct 110 ms 21840 KB Output is correct
29 Correct 133 ms 21644 KB Output is correct
30 Correct 118 ms 21684 KB Output is correct
31 Correct 2677 ms 97144 KB Output is correct
32 Correct 2634 ms 109584 KB Output is correct
33 Correct 2579 ms 96972 KB Output is correct
34 Correct 2191 ms 106644 KB Output is correct
35 Execution timed out 6047 ms 88460 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 16276 KB Output is correct
2 Correct 113 ms 21944 KB Output is correct
3 Correct 108 ms 21784 KB Output is correct
4 Correct 143 ms 21928 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 134 ms 21756 KB Output is correct
7 Correct 72 ms 16256 KB Output is correct
8 Correct 121 ms 21860 KB Output is correct
9 Correct 140 ms 21764 KB Output is correct
10 Correct 135 ms 21744 KB Output is correct
11 Correct 12 ms 14548 KB Output is correct
12 Correct 115 ms 21712 KB Output is correct
13 Correct 108 ms 21580 KB Output is correct
14 Correct 125 ms 21668 KB Output is correct
15 Correct 104 ms 21588 KB Output is correct
16 Correct 116 ms 21832 KB Output is correct
17 Correct 120 ms 21676 KB Output is correct
18 Correct 120 ms 21656 KB Output is correct
19 Correct 73 ms 16280 KB Output is correct
20 Correct 143 ms 21772 KB Output is correct
21 Correct 121 ms 21716 KB Output is correct
22 Correct 139 ms 21788 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 124 ms 21828 KB Output is correct
25 Correct 119 ms 21608 KB Output is correct
26 Correct 109 ms 21644 KB Output is correct
27 Correct 103 ms 21716 KB Output is correct
28 Correct 110 ms 21840 KB Output is correct
29 Correct 133 ms 21644 KB Output is correct
30 Correct 118 ms 21684 KB Output is correct
31 Correct 2677 ms 97144 KB Output is correct
32 Correct 2634 ms 109584 KB Output is correct
33 Correct 2579 ms 96972 KB Output is correct
34 Correct 2191 ms 106644 KB Output is correct
35 Execution timed out 6047 ms 88460 KB Time limit exceeded
36 Halted 0 ms 0 KB -