oj.uz

Submission #657487

# Submission time Handle Problem Language Result Execution time Memory
657487 2022-11-10T01:39:12 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 109740 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
                    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)));
                        }
                    }
                    int d1 = d[u][t]+1;
                    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)));
                    }
                }
                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 129 ms 16280 KB Output is correct
2 Correct 120 ms 21844 KB Output is correct
3 Correct 111 ms 21732 KB Output is correct
4 Correct 131 ms 21836 KB Output is correct
5 Correct 11 ms 14484 KB Output is correct
6 Correct 117 ms 21760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 16280 KB Output is correct
2 Correct 100 ms 21840 KB Output is correct
3 Correct 102 ms 21708 KB Output is correct
4 Correct 176 ms 21796 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 103 ms 21724 KB Output is correct
7 Correct 100 ms 21596 KB Output is correct
8 Correct 109 ms 21660 KB Output is correct
9 Correct 103 ms 21516 KB Output is correct
10 Correct 114 ms 21900 KB Output is correct
11 Correct 116 ms 21684 KB Output is correct
12 Correct 107 ms 21644 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 16280 KB Output is correct
2 Correct 100 ms 21840 KB Output is correct
3 Correct 102 ms 21708 KB Output is correct
4 Correct 176 ms 21796 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 103 ms 21724 KB Output is correct
7 Correct 100 ms 21596 KB Output is correct
8 Correct 109 ms 21660 KB Output is correct
9 Correct 103 ms 21516 KB Output is correct
10 Correct 114 ms 21900 KB Output is correct
11 Correct 116 ms 21684 KB Output is correct
12 Correct 107 ms 21644 KB Output is correct
13 Correct 129 ms 16284 KB Output is correct
14 Correct 103 ms 21792 KB Output is correct
15 Correct 116 ms 21720 KB Output is correct
16 Correct 130 ms 21796 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 113 ms 21724 KB Output is correct
19 Correct 107 ms 21712 KB Output is correct
20 Correct 105 ms 21636 KB Output is correct
21 Correct 111 ms 21684 KB Output is correct
22 Correct 121 ms 21860 KB Output is correct
23 Correct 116 ms 21756 KB Output is correct
24 Correct 102 ms 21660 KB Output is correct
25 Correct 2527 ms 97212 KB Output is correct
26 Correct 2544 ms 109740 KB Output is correct
27 Correct 2296 ms 96912 KB Output is correct
28 Correct 2033 ms 106692 KB Output is correct
29 Execution timed out 6073 ms 88608 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 16280 KB Output is correct
2 Correct 100 ms 21840 KB Output is correct
3 Correct 102 ms 21708 KB Output is correct
4 Correct 176 ms 21796 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 103 ms 21724 KB Output is correct
7 Correct 100 ms 21596 KB Output is correct
8 Correct 109 ms 21660 KB Output is correct
9 Correct 103 ms 21516 KB Output is correct
10 Correct 114 ms 21900 KB Output is correct
11 Correct 116 ms 21684 KB Output is correct
12 Correct 107 ms 21644 KB Output is correct
13 Correct 129 ms 16284 KB Output is correct
14 Correct 103 ms 21792 KB Output is correct
15 Correct 116 ms 21720 KB Output is correct
16 Correct 130 ms 21796 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 113 ms 21724 KB Output is correct
19 Correct 107 ms 21712 KB Output is correct
20 Correct 105 ms 21636 KB Output is correct
21 Correct 111 ms 21684 KB Output is correct
22 Correct 121 ms 21860 KB Output is correct
23 Correct 116 ms 21756 KB Output is correct
24 Correct 102 ms 21660 KB Output is correct
25 Correct 2527 ms 97212 KB Output is correct
26 Correct 2544 ms 109740 KB Output is correct
27 Correct 2296 ms 96912 KB Output is correct
28 Correct 2033 ms 106692 KB Output is correct
29 Execution timed out 6073 ms 88608 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16280 KB Output is correct
2 Correct 120 ms 21844 KB Output is correct
3 Correct 111 ms 21732 KB Output is correct
4 Correct 131 ms 21836 KB Output is correct
5 Correct 11 ms 14484 KB Output is correct
6 Correct 117 ms 21760 KB Output is correct
7 Correct 131 ms 16280 KB Output is correct
8 Correct 100 ms 21840 KB Output is correct
9 Correct 102 ms 21708 KB Output is correct
10 Correct 176 ms 21796 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 103 ms 21724 KB Output is correct
13 Correct 100 ms 21596 KB Output is correct
14 Correct 109 ms 21660 KB Output is correct
15 Correct 103 ms 21516 KB Output is correct
16 Correct 114 ms 21900 KB Output is correct
17 Correct 116 ms 21684 KB Output is correct
18 Correct 107 ms 21644 KB Output is correct
19 Correct 7 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 130 ms 16276 KB Output is correct
23 Correct 104 ms 21760 KB Output is correct
24 Correct 107 ms 21744 KB Output is correct
25 Correct 156 ms 21864 KB Output is correct
26 Correct 9 ms 14456 KB Output is correct
27 Correct 101 ms 21708 KB Output is correct
28 Correct 100 ms 21592 KB Output is correct
29 Correct 100 ms 21652 KB Output is correct
30 Correct 112 ms 21588 KB Output is correct
31 Correct 123 ms 21900 KB Output is correct
32 Correct 103 ms 21628 KB Output is correct
33 Correct 123 ms 21708 KB Output is correct
34 Correct 2715 ms 98532 KB Output is correct
35 Correct 2785 ms 91624 KB Output is correct
36 Correct 2612 ms 91708 KB Output is correct
37 Incorrect 2350 ms 104152 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16280 KB Output is correct
2 Correct 120 ms 21844 KB Output is correct
3 Correct 111 ms 21732 KB Output is correct
4 Correct 131 ms 21836 KB Output is correct
5 Correct 11 ms 14484 KB Output is correct
6 Correct 117 ms 21760 KB Output is correct
7 Correct 131 ms 16280 KB Output is correct
8 Correct 100 ms 21840 KB Output is correct
9 Correct 102 ms 21708 KB Output is correct
10 Correct 176 ms 21796 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 103 ms 21724 KB Output is correct
13 Correct 100 ms 21596 KB Output is correct
14 Correct 109 ms 21660 KB Output is correct
15 Correct 103 ms 21516 KB Output is correct
16 Correct 114 ms 21900 KB Output is correct
17 Correct 116 ms 21684 KB Output is correct
18 Correct 107 ms 21644 KB Output is correct
19 Correct 129 ms 16284 KB Output is correct
20 Correct 103 ms 21792 KB Output is correct
21 Correct 116 ms 21720 KB Output is correct
22 Correct 130 ms 21796 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 113 ms 21724 KB Output is correct
25 Correct 107 ms 21712 KB Output is correct
26 Correct 105 ms 21636 KB Output is correct
27 Correct 111 ms 21684 KB Output is correct
28 Correct 121 ms 21860 KB Output is correct
29 Correct 116 ms 21756 KB Output is correct
30 Correct 102 ms 21660 KB Output is correct
31 Correct 2527 ms 97212 KB Output is correct
32 Correct 2544 ms 109740 KB Output is correct
33 Correct 2296 ms 96912 KB Output is correct
34 Correct 2033 ms 106692 KB Output is correct
35 Execution timed out 6073 ms 88608 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16280 KB Output is correct
2 Correct 120 ms 21844 KB Output is correct
3 Correct 111 ms 21732 KB Output is correct
4 Correct 131 ms 21836 KB Output is correct
5 Correct 11 ms 14484 KB Output is correct
6 Correct 117 ms 21760 KB Output is correct
7 Correct 131 ms 16280 KB Output is correct
8 Correct 100 ms 21840 KB Output is correct
9 Correct 102 ms 21708 KB Output is correct
10 Correct 176 ms 21796 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 103 ms 21724 KB Output is correct
13 Correct 100 ms 21596 KB Output is correct
14 Correct 109 ms 21660 KB Output is correct
15 Correct 103 ms 21516 KB Output is correct
16 Correct 114 ms 21900 KB Output is correct
17 Correct 116 ms 21684 KB Output is correct
18 Correct 107 ms 21644 KB Output is correct
19 Correct 129 ms 16284 KB Output is correct
20 Correct 103 ms 21792 KB Output is correct
21 Correct 116 ms 21720 KB Output is correct
22 Correct 130 ms 21796 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 113 ms 21724 KB Output is correct
25 Correct 107 ms 21712 KB Output is correct
26 Correct 105 ms 21636 KB Output is correct
27 Correct 111 ms 21684 KB Output is correct
28 Correct 121 ms 21860 KB Output is correct
29 Correct 116 ms 21756 KB Output is correct
30 Correct 102 ms 21660 KB Output is correct
31 Correct 2527 ms 97212 KB Output is correct
32 Correct 2544 ms 109740 KB Output is correct
33 Correct 2296 ms 96912 KB Output is correct
34 Correct 2033 ms 106692 KB Output is correct
35 Execution timed out 6073 ms 88608 KB Time limit exceeded
36 Halted 0 ms 0 KB -