oj.uz

Submission #657498

# Submission time Handle Problem Language Result Execution time Memory
657498 2022-11-10T01:54:22 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 69768 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], dlol[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++) {
        dlol[i] = inf;
        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(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]) continue;
                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)));
                }
            }
            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)));
                    }
                }
                if(dlol[u] > d[u][t]+1) {
                    dlol[u] = d[u][t]+1;
                    pq.push(mp(dlol[u],mp(u,-1)));
                }
            }
        }
        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)));
                    }
                    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 78 ms 15284 KB Output is correct
2 Correct 115 ms 21884 KB Output is correct
3 Correct 99 ms 21456 KB Output is correct
4 Correct 148 ms 21520 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 100 ms 21320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15360 KB Output is correct
2 Correct 114 ms 21944 KB Output is correct
3 Correct 100 ms 21376 KB Output is correct
4 Correct 131 ms 21584 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 105 ms 21436 KB Output is correct
7 Correct 109 ms 21356 KB Output is correct
8 Correct 103 ms 21324 KB Output is correct
9 Correct 96 ms 21272 KB Output is correct
10 Correct 109 ms 21572 KB Output is correct
11 Correct 101 ms 21356 KB Output is correct
12 Correct 101 ms 21356 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15360 KB Output is correct
2 Correct 114 ms 21944 KB Output is correct
3 Correct 100 ms 21376 KB Output is correct
4 Correct 131 ms 21584 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 105 ms 21436 KB Output is correct
7 Correct 109 ms 21356 KB Output is correct
8 Correct 103 ms 21324 KB Output is correct
9 Correct 96 ms 21272 KB Output is correct
10 Correct 109 ms 21572 KB Output is correct
11 Correct 101 ms 21356 KB Output is correct
12 Correct 101 ms 21356 KB Output is correct
13 Correct 78 ms 15356 KB Output is correct
14 Correct 109 ms 21964 KB Output is correct
15 Correct 103 ms 21440 KB Output is correct
16 Correct 131 ms 21452 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 108 ms 21340 KB Output is correct
19 Correct 102 ms 21356 KB Output is correct
20 Correct 102 ms 21336 KB Output is correct
21 Correct 113 ms 21264 KB Output is correct
22 Correct 107 ms 21584 KB Output is correct
23 Correct 99 ms 21324 KB Output is correct
24 Correct 102 ms 21348 KB Output is correct
25 Correct 2588 ms 65016 KB Output is correct
26 Correct 2425 ms 69768 KB Output is correct
27 Correct 2472 ms 65556 KB Output is correct
28 Correct 2053 ms 69556 KB Output is correct
29 Execution timed out 6088 ms 60376 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15360 KB Output is correct
2 Correct 114 ms 21944 KB Output is correct
3 Correct 100 ms 21376 KB Output is correct
4 Correct 131 ms 21584 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 105 ms 21436 KB Output is correct
7 Correct 109 ms 21356 KB Output is correct
8 Correct 103 ms 21324 KB Output is correct
9 Correct 96 ms 21272 KB Output is correct
10 Correct 109 ms 21572 KB Output is correct
11 Correct 101 ms 21356 KB Output is correct
12 Correct 101 ms 21356 KB Output is correct
13 Correct 78 ms 15356 KB Output is correct
14 Correct 109 ms 21964 KB Output is correct
15 Correct 103 ms 21440 KB Output is correct
16 Correct 131 ms 21452 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 108 ms 21340 KB Output is correct
19 Correct 102 ms 21356 KB Output is correct
20 Correct 102 ms 21336 KB Output is correct
21 Correct 113 ms 21264 KB Output is correct
22 Correct 107 ms 21584 KB Output is correct
23 Correct 99 ms 21324 KB Output is correct
24 Correct 102 ms 21348 KB Output is correct
25 Correct 2588 ms 65016 KB Output is correct
26 Correct 2425 ms 69768 KB Output is correct
27 Correct 2472 ms 65556 KB Output is correct
28 Correct 2053 ms 69556 KB Output is correct
29 Execution timed out 6088 ms 60376 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15284 KB Output is correct
2 Correct 115 ms 21884 KB Output is correct
3 Correct 99 ms 21456 KB Output is correct
4 Correct 148 ms 21520 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 100 ms 21320 KB Output is correct
7 Correct 73 ms 15360 KB Output is correct
8 Correct 114 ms 21944 KB Output is correct
9 Correct 100 ms 21376 KB Output is correct
10 Correct 131 ms 21584 KB Output is correct
11 Correct 9 ms 14464 KB Output is correct
12 Correct 105 ms 21436 KB Output is correct
13 Correct 109 ms 21356 KB Output is correct
14 Correct 103 ms 21324 KB Output is correct
15 Correct 96 ms 21272 KB Output is correct
16 Correct 109 ms 21572 KB Output is correct
17 Correct 101 ms 21356 KB Output is correct
18 Correct 101 ms 21356 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 75 ms 15260 KB Output is correct
23 Correct 104 ms 21848 KB Output is correct
24 Correct 105 ms 21452 KB Output is correct
25 Correct 122 ms 21448 KB Output is correct
26 Correct 9 ms 14420 KB Output is correct
27 Correct 106 ms 21284 KB Output is correct
28 Correct 99 ms 21340 KB Output is correct
29 Correct 101 ms 21388 KB Output is correct
30 Correct 133 ms 21236 KB Output is correct
31 Correct 129 ms 21612 KB Output is correct
32 Correct 109 ms 21412 KB Output is correct
33 Correct 109 ms 21356 KB Output is correct
34 Correct 2848 ms 65344 KB Output is correct
35 Correct 2932 ms 62116 KB Output is correct
36 Correct 2691 ms 62096 KB Output is correct
37 Incorrect 2434 ms 67272 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15284 KB Output is correct
2 Correct 115 ms 21884 KB Output is correct
3 Correct 99 ms 21456 KB Output is correct
4 Correct 148 ms 21520 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 100 ms 21320 KB Output is correct
7 Correct 73 ms 15360 KB Output is correct
8 Correct 114 ms 21944 KB Output is correct
9 Correct 100 ms 21376 KB Output is correct
10 Correct 131 ms 21584 KB Output is correct
11 Correct 9 ms 14464 KB Output is correct
12 Correct 105 ms 21436 KB Output is correct
13 Correct 109 ms 21356 KB Output is correct
14 Correct 103 ms 21324 KB Output is correct
15 Correct 96 ms 21272 KB Output is correct
16 Correct 109 ms 21572 KB Output is correct
17 Correct 101 ms 21356 KB Output is correct
18 Correct 101 ms 21356 KB Output is correct
19 Correct 78 ms 15356 KB Output is correct
20 Correct 109 ms 21964 KB Output is correct
21 Correct 103 ms 21440 KB Output is correct
22 Correct 131 ms 21452 KB Output is correct
23 Correct 8 ms 14420 KB Output is correct
24 Correct 108 ms 21340 KB Output is correct
25 Correct 102 ms 21356 KB Output is correct
26 Correct 102 ms 21336 KB Output is correct
27 Correct 113 ms 21264 KB Output is correct
28 Correct 107 ms 21584 KB Output is correct
29 Correct 99 ms 21324 KB Output is correct
30 Correct 102 ms 21348 KB Output is correct
31 Correct 2588 ms 65016 KB Output is correct
32 Correct 2425 ms 69768 KB Output is correct
33 Correct 2472 ms 65556 KB Output is correct
34 Correct 2053 ms 69556 KB Output is correct
35 Execution timed out 6088 ms 60376 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15284 KB Output is correct
2 Correct 115 ms 21884 KB Output is correct
3 Correct 99 ms 21456 KB Output is correct
4 Correct 148 ms 21520 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 100 ms 21320 KB Output is correct
7 Correct 73 ms 15360 KB Output is correct
8 Correct 114 ms 21944 KB Output is correct
9 Correct 100 ms 21376 KB Output is correct
10 Correct 131 ms 21584 KB Output is correct
11 Correct 9 ms 14464 KB Output is correct
12 Correct 105 ms 21436 KB Output is correct
13 Correct 109 ms 21356 KB Output is correct
14 Correct 103 ms 21324 KB Output is correct
15 Correct 96 ms 21272 KB Output is correct
16 Correct 109 ms 21572 KB Output is correct
17 Correct 101 ms 21356 KB Output is correct
18 Correct 101 ms 21356 KB Output is correct
19 Correct 78 ms 15356 KB Output is correct
20 Correct 109 ms 21964 KB Output is correct
21 Correct 103 ms 21440 KB Output is correct
22 Correct 131 ms 21452 KB Output is correct
23 Correct 8 ms 14420 KB Output is correct
24 Correct 108 ms 21340 KB Output is correct
25 Correct 102 ms 21356 KB Output is correct
26 Correct 102 ms 21336 KB Output is correct
27 Correct 113 ms 21264 KB Output is correct
28 Correct 107 ms 21584 KB Output is correct
29 Correct 99 ms 21324 KB Output is correct
30 Correct 102 ms 21348 KB Output is correct
31 Correct 2588 ms 65016 KB Output is correct
32 Correct 2425 ms 69768 KB Output is correct
33 Correct 2472 ms 65556 KB Output is correct
34 Correct 2053 ms 69556 KB Output is correct
35 Execution timed out 6088 ms 60376 KB Time limit exceeded
36 Halted 0 ms 0 KB -