oj.uz

Submission #657486

# Submission time Handle Problem Language Result Execution time Memory
657486 2022-11-10T01:35:42 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 110080 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]) {
                    for(int i = 0; i < szrt[idrt[v]]; i++) {
                        int d1 = d[u][t]+1+i;
                        int t1 = d1%szrt[idrt[v]];
                        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 117 ms 16536 KB Output is correct
2 Correct 127 ms 22108 KB Output is correct
3 Correct 119 ms 22000 KB Output is correct
4 Correct 145 ms 22072 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 132 ms 22012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16540 KB Output is correct
2 Correct 115 ms 22104 KB Output is correct
3 Correct 123 ms 22012 KB Output is correct
4 Correct 141 ms 22084 KB Output is correct
5 Correct 10 ms 14516 KB Output is correct
6 Correct 112 ms 21968 KB Output is correct
7 Correct 108 ms 21972 KB Output is correct
8 Correct 106 ms 21988 KB Output is correct
9 Correct 120 ms 21872 KB Output is correct
10 Correct 124 ms 22160 KB Output is correct
11 Correct 112 ms 21960 KB Output is correct
12 Correct 112 ms 21912 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16540 KB Output is correct
2 Correct 115 ms 22104 KB Output is correct
3 Correct 123 ms 22012 KB Output is correct
4 Correct 141 ms 22084 KB Output is correct
5 Correct 10 ms 14516 KB Output is correct
6 Correct 112 ms 21968 KB Output is correct
7 Correct 108 ms 21972 KB Output is correct
8 Correct 106 ms 21988 KB Output is correct
9 Correct 120 ms 21872 KB Output is correct
10 Correct 124 ms 22160 KB Output is correct
11 Correct 112 ms 21960 KB Output is correct
12 Correct 112 ms 21912 KB Output is correct
13 Correct 115 ms 16532 KB Output is correct
14 Correct 105 ms 22068 KB Output is correct
15 Correct 104 ms 22000 KB Output is correct
16 Correct 143 ms 22092 KB Output is correct
17 Correct 9 ms 14472 KB Output is correct
18 Correct 119 ms 21988 KB Output is correct
19 Correct 97 ms 21824 KB Output is correct
20 Correct 105 ms 21824 KB Output is correct
21 Correct 119 ms 21872 KB Output is correct
22 Correct 132 ms 22128 KB Output is correct
23 Correct 115 ms 21892 KB Output is correct
24 Correct 125 ms 21912 KB Output is correct
25 Correct 2588 ms 97328 KB Output is correct
26 Correct 2612 ms 110080 KB Output is correct
27 Correct 2499 ms 97432 KB Output is correct
28 Correct 2157 ms 106872 KB Output is correct
29 Execution timed out 6107 ms 88644 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16540 KB Output is correct
2 Correct 115 ms 22104 KB Output is correct
3 Correct 123 ms 22012 KB Output is correct
4 Correct 141 ms 22084 KB Output is correct
5 Correct 10 ms 14516 KB Output is correct
6 Correct 112 ms 21968 KB Output is correct
7 Correct 108 ms 21972 KB Output is correct
8 Correct 106 ms 21988 KB Output is correct
9 Correct 120 ms 21872 KB Output is correct
10 Correct 124 ms 22160 KB Output is correct
11 Correct 112 ms 21960 KB Output is correct
12 Correct 112 ms 21912 KB Output is correct
13 Correct 115 ms 16532 KB Output is correct
14 Correct 105 ms 22068 KB Output is correct
15 Correct 104 ms 22000 KB Output is correct
16 Correct 143 ms 22092 KB Output is correct
17 Correct 9 ms 14472 KB Output is correct
18 Correct 119 ms 21988 KB Output is correct
19 Correct 97 ms 21824 KB Output is correct
20 Correct 105 ms 21824 KB Output is correct
21 Correct 119 ms 21872 KB Output is correct
22 Correct 132 ms 22128 KB Output is correct
23 Correct 115 ms 21892 KB Output is correct
24 Correct 125 ms 21912 KB Output is correct
25 Correct 2588 ms 97328 KB Output is correct
26 Correct 2612 ms 110080 KB Output is correct
27 Correct 2499 ms 97432 KB Output is correct
28 Correct 2157 ms 106872 KB Output is correct
29 Execution timed out 6107 ms 88644 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16536 KB Output is correct
2 Correct 127 ms 22108 KB Output is correct
3 Correct 119 ms 22000 KB Output is correct
4 Correct 145 ms 22072 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 132 ms 22012 KB Output is correct
7 Correct 113 ms 16540 KB Output is correct
8 Correct 115 ms 22104 KB Output is correct
9 Correct 123 ms 22012 KB Output is correct
10 Correct 141 ms 22084 KB Output is correct
11 Correct 10 ms 14516 KB Output is correct
12 Correct 112 ms 21968 KB Output is correct
13 Correct 108 ms 21972 KB Output is correct
14 Correct 106 ms 21988 KB Output is correct
15 Correct 120 ms 21872 KB Output is correct
16 Correct 124 ms 22160 KB Output is correct
17 Correct 112 ms 21960 KB Output is correct
18 Correct 112 ms 21912 KB Output is correct
19 Correct 8 ms 14400 KB Output is correct
20 Correct 9 ms 14420 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 118 ms 16424 KB Output is correct
23 Correct 125 ms 22112 KB Output is correct
24 Correct 110 ms 21976 KB Output is correct
25 Correct 140 ms 22056 KB Output is correct
26 Correct 9 ms 14548 KB Output is correct
27 Correct 120 ms 22104 KB Output is correct
28 Correct 106 ms 21868 KB Output is correct
29 Correct 104 ms 21888 KB Output is correct
30 Correct 98 ms 21848 KB Output is correct
31 Correct 121 ms 22176 KB Output is correct
32 Correct 118 ms 21900 KB Output is correct
33 Correct 108 ms 21904 KB Output is correct
34 Correct 2609 ms 98544 KB Output is correct
35 Correct 2636 ms 91832 KB Output is correct
36 Correct 2646 ms 91596 KB Output is correct
37 Incorrect 2396 ms 104384 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16536 KB Output is correct
2 Correct 127 ms 22108 KB Output is correct
3 Correct 119 ms 22000 KB Output is correct
4 Correct 145 ms 22072 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 132 ms 22012 KB Output is correct
7 Correct 113 ms 16540 KB Output is correct
8 Correct 115 ms 22104 KB Output is correct
9 Correct 123 ms 22012 KB Output is correct
10 Correct 141 ms 22084 KB Output is correct
11 Correct 10 ms 14516 KB Output is correct
12 Correct 112 ms 21968 KB Output is correct
13 Correct 108 ms 21972 KB Output is correct
14 Correct 106 ms 21988 KB Output is correct
15 Correct 120 ms 21872 KB Output is correct
16 Correct 124 ms 22160 KB Output is correct
17 Correct 112 ms 21960 KB Output is correct
18 Correct 112 ms 21912 KB Output is correct
19 Correct 115 ms 16532 KB Output is correct
20 Correct 105 ms 22068 KB Output is correct
21 Correct 104 ms 22000 KB Output is correct
22 Correct 143 ms 22092 KB Output is correct
23 Correct 9 ms 14472 KB Output is correct
24 Correct 119 ms 21988 KB Output is correct
25 Correct 97 ms 21824 KB Output is correct
26 Correct 105 ms 21824 KB Output is correct
27 Correct 119 ms 21872 KB Output is correct
28 Correct 132 ms 22128 KB Output is correct
29 Correct 115 ms 21892 KB Output is correct
30 Correct 125 ms 21912 KB Output is correct
31 Correct 2588 ms 97328 KB Output is correct
32 Correct 2612 ms 110080 KB Output is correct
33 Correct 2499 ms 97432 KB Output is correct
34 Correct 2157 ms 106872 KB Output is correct
35 Execution timed out 6107 ms 88644 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16536 KB Output is correct
2 Correct 127 ms 22108 KB Output is correct
3 Correct 119 ms 22000 KB Output is correct
4 Correct 145 ms 22072 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 132 ms 22012 KB Output is correct
7 Correct 113 ms 16540 KB Output is correct
8 Correct 115 ms 22104 KB Output is correct
9 Correct 123 ms 22012 KB Output is correct
10 Correct 141 ms 22084 KB Output is correct
11 Correct 10 ms 14516 KB Output is correct
12 Correct 112 ms 21968 KB Output is correct
13 Correct 108 ms 21972 KB Output is correct
14 Correct 106 ms 21988 KB Output is correct
15 Correct 120 ms 21872 KB Output is correct
16 Correct 124 ms 22160 KB Output is correct
17 Correct 112 ms 21960 KB Output is correct
18 Correct 112 ms 21912 KB Output is correct
19 Correct 115 ms 16532 KB Output is correct
20 Correct 105 ms 22068 KB Output is correct
21 Correct 104 ms 22000 KB Output is correct
22 Correct 143 ms 22092 KB Output is correct
23 Correct 9 ms 14472 KB Output is correct
24 Correct 119 ms 21988 KB Output is correct
25 Correct 97 ms 21824 KB Output is correct
26 Correct 105 ms 21824 KB Output is correct
27 Correct 119 ms 21872 KB Output is correct
28 Correct 132 ms 22128 KB Output is correct
29 Correct 115 ms 21892 KB Output is correct
30 Correct 125 ms 21912 KB Output is correct
31 Correct 2588 ms 97328 KB Output is correct
32 Correct 2612 ms 110080 KB Output is correct
33 Correct 2499 ms 97432 KB Output is correct
34 Correct 2157 ms 106872 KB Output is correct
35 Execution timed out 6107 ms 88644 KB Time limit exceeded
36 Halted 0 ms 0 KB -