oj.uz

Submission #657485

# Submission time Handle Problem Language Result Execution time Memory
657485 2022-11-10T01:33:18 Z Lobo From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 123456 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]) 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 91 ms 17332 KB Output is correct
2 Correct 107 ms 23008 KB Output is correct
3 Correct 106 ms 23140 KB Output is correct
4 Correct 138 ms 23500 KB Output is correct
5 Correct 10 ms 14548 KB Output is correct
6 Correct 106 ms 23120 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 17332 KB Output is correct
2 Correct 112 ms 23016 KB Output is correct
3 Correct 106 ms 23100 KB Output is correct
4 Correct 145 ms 23652 KB Output is correct
5 Correct 10 ms 14484 KB Output is correct
6 Correct 106 ms 23068 KB Output is correct
7 Correct 98 ms 22732 KB Output is correct
8 Correct 104 ms 22788 KB Output is correct
9 Correct 100 ms 22720 KB Output is correct
10 Correct 110 ms 23032 KB Output is correct
11 Correct 103 ms 22860 KB Output is correct
12 Correct 103 ms 22796 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 17332 KB Output is correct
2 Correct 112 ms 23016 KB Output is correct
3 Correct 106 ms 23100 KB Output is correct
4 Correct 145 ms 23652 KB Output is correct
5 Correct 10 ms 14484 KB Output is correct
6 Correct 106 ms 23068 KB Output is correct
7 Correct 98 ms 22732 KB Output is correct
8 Correct 104 ms 22788 KB Output is correct
9 Correct 100 ms 22720 KB Output is correct
10 Correct 110 ms 23032 KB Output is correct
11 Correct 103 ms 22860 KB Output is correct
12 Correct 103 ms 22796 KB Output is correct
13 Correct 92 ms 17332 KB Output is correct
14 Correct 106 ms 23016 KB Output is correct
15 Correct 104 ms 23096 KB Output is correct
16 Correct 136 ms 23608 KB Output is correct
17 Correct 10 ms 14548 KB Output is correct
18 Correct 112 ms 23104 KB Output is correct
19 Correct 113 ms 22848 KB Output is correct
20 Correct 105 ms 22816 KB Output is correct
21 Correct 99 ms 22736 KB Output is correct
22 Correct 114 ms 23036 KB Output is correct
23 Correct 105 ms 22860 KB Output is correct
24 Correct 112 ms 22876 KB Output is correct
25 Correct 2602 ms 110900 KB Output is correct
26 Correct 2560 ms 123456 KB Output is correct
27 Correct 2409 ms 111556 KB Output is correct
28 Correct 2078 ms 120580 KB Output is correct
29 Execution timed out 6020 ms 105512 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 17332 KB Output is correct
2 Correct 112 ms 23016 KB Output is correct
3 Correct 106 ms 23100 KB Output is correct
4 Correct 145 ms 23652 KB Output is correct
5 Correct 10 ms 14484 KB Output is correct
6 Correct 106 ms 23068 KB Output is correct
7 Correct 98 ms 22732 KB Output is correct
8 Correct 104 ms 22788 KB Output is correct
9 Correct 100 ms 22720 KB Output is correct
10 Correct 110 ms 23032 KB Output is correct
11 Correct 103 ms 22860 KB Output is correct
12 Correct 103 ms 22796 KB Output is correct
13 Correct 92 ms 17332 KB Output is correct
14 Correct 106 ms 23016 KB Output is correct
15 Correct 104 ms 23096 KB Output is correct
16 Correct 136 ms 23608 KB Output is correct
17 Correct 10 ms 14548 KB Output is correct
18 Correct 112 ms 23104 KB Output is correct
19 Correct 113 ms 22848 KB Output is correct
20 Correct 105 ms 22816 KB Output is correct
21 Correct 99 ms 22736 KB Output is correct
22 Correct 114 ms 23036 KB Output is correct
23 Correct 105 ms 22860 KB Output is correct
24 Correct 112 ms 22876 KB Output is correct
25 Correct 2602 ms 110900 KB Output is correct
26 Correct 2560 ms 123456 KB Output is correct
27 Correct 2409 ms 111556 KB Output is correct
28 Correct 2078 ms 120580 KB Output is correct
29 Execution timed out 6020 ms 105512 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17332 KB Output is correct
2 Correct 107 ms 23008 KB Output is correct
3 Correct 106 ms 23140 KB Output is correct
4 Correct 138 ms 23500 KB Output is correct
5 Correct 10 ms 14548 KB Output is correct
6 Correct 106 ms 23120 KB Output is correct
7 Correct 94 ms 17332 KB Output is correct
8 Correct 112 ms 23016 KB Output is correct
9 Correct 106 ms 23100 KB Output is correct
10 Correct 145 ms 23652 KB Output is correct
11 Correct 10 ms 14484 KB Output is correct
12 Correct 106 ms 23068 KB Output is correct
13 Correct 98 ms 22732 KB Output is correct
14 Correct 104 ms 22788 KB Output is correct
15 Correct 100 ms 22720 KB Output is correct
16 Correct 110 ms 23032 KB Output is correct
17 Correct 103 ms 22860 KB Output is correct
18 Correct 103 ms 22796 KB Output is correct
19 Correct 7 ms 14404 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 92 ms 17292 KB Output is correct
23 Correct 106 ms 22984 KB Output is correct
24 Correct 125 ms 23104 KB Output is correct
25 Correct 143 ms 23536 KB Output is correct
26 Correct 9 ms 14548 KB Output is correct
27 Correct 104 ms 23140 KB Output is correct
28 Correct 106 ms 22732 KB Output is correct
29 Correct 100 ms 22752 KB Output is correct
30 Correct 105 ms 22776 KB Output is correct
31 Correct 116 ms 23056 KB Output is correct
32 Correct 102 ms 22876 KB Output is correct
33 Correct 102 ms 22812 KB Output is correct
34 Correct 2673 ms 113356 KB Output is correct
35 Correct 2688 ms 106548 KB Output is correct
36 Correct 2705 ms 106700 KB Output is correct
37 Incorrect 2451 ms 119492 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17332 KB Output is correct
2 Correct 107 ms 23008 KB Output is correct
3 Correct 106 ms 23140 KB Output is correct
4 Correct 138 ms 23500 KB Output is correct
5 Correct 10 ms 14548 KB Output is correct
6 Correct 106 ms 23120 KB Output is correct
7 Correct 94 ms 17332 KB Output is correct
8 Correct 112 ms 23016 KB Output is correct
9 Correct 106 ms 23100 KB Output is correct
10 Correct 145 ms 23652 KB Output is correct
11 Correct 10 ms 14484 KB Output is correct
12 Correct 106 ms 23068 KB Output is correct
13 Correct 98 ms 22732 KB Output is correct
14 Correct 104 ms 22788 KB Output is correct
15 Correct 100 ms 22720 KB Output is correct
16 Correct 110 ms 23032 KB Output is correct
17 Correct 103 ms 22860 KB Output is correct
18 Correct 103 ms 22796 KB Output is correct
19 Correct 92 ms 17332 KB Output is correct
20 Correct 106 ms 23016 KB Output is correct
21 Correct 104 ms 23096 KB Output is correct
22 Correct 136 ms 23608 KB Output is correct
23 Correct 10 ms 14548 KB Output is correct
24 Correct 112 ms 23104 KB Output is correct
25 Correct 113 ms 22848 KB Output is correct
26 Correct 105 ms 22816 KB Output is correct
27 Correct 99 ms 22736 KB Output is correct
28 Correct 114 ms 23036 KB Output is correct
29 Correct 105 ms 22860 KB Output is correct
30 Correct 112 ms 22876 KB Output is correct
31 Correct 2602 ms 110900 KB Output is correct
32 Correct 2560 ms 123456 KB Output is correct
33 Correct 2409 ms 111556 KB Output is correct
34 Correct 2078 ms 120580 KB Output is correct
35 Execution timed out 6020 ms 105512 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17332 KB Output is correct
2 Correct 107 ms 23008 KB Output is correct
3 Correct 106 ms 23140 KB Output is correct
4 Correct 138 ms 23500 KB Output is correct
5 Correct 10 ms 14548 KB Output is correct
6 Correct 106 ms 23120 KB Output is correct
7 Correct 94 ms 17332 KB Output is correct
8 Correct 112 ms 23016 KB Output is correct
9 Correct 106 ms 23100 KB Output is correct
10 Correct 145 ms 23652 KB Output is correct
11 Correct 10 ms 14484 KB Output is correct
12 Correct 106 ms 23068 KB Output is correct
13 Correct 98 ms 22732 KB Output is correct
14 Correct 104 ms 22788 KB Output is correct
15 Correct 100 ms 22720 KB Output is correct
16 Correct 110 ms 23032 KB Output is correct
17 Correct 103 ms 22860 KB Output is correct
18 Correct 103 ms 22796 KB Output is correct
19 Correct 92 ms 17332 KB Output is correct
20 Correct 106 ms 23016 KB Output is correct
21 Correct 104 ms 23096 KB Output is correct
22 Correct 136 ms 23608 KB Output is correct
23 Correct 10 ms 14548 KB Output is correct
24 Correct 112 ms 23104 KB Output is correct
25 Correct 113 ms 22848 KB Output is correct
26 Correct 105 ms 22816 KB Output is correct
27 Correct 99 ms 22736 KB Output is correct
28 Correct 114 ms 23036 KB Output is correct
29 Correct 105 ms 22860 KB Output is correct
30 Correct 112 ms 22876 KB Output is correct
31 Correct 2602 ms 110900 KB Output is correct
32 Correct 2560 ms 123456 KB Output is correct
33 Correct 2409 ms 111556 KB Output is correct
34 Correct 2078 ms 120580 KB Output is correct
35 Execution timed out 6020 ms 105512 KB Time limit exceeded
36 Halted 0 ms 0 KB -