oj.uz

Submission #540493

# Submission time Handle Problem Language Result Execution time Memory
540493 2022-03-20T13:54:04 Z elazarkoren From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 135408 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;

const int MAX_N = 3e5;
const int MAX_L = 3e5;
const int infinity = 1e9;

int Gcd(int a, int b) {
    return (b ? Gcd(b, a % b) : a);
}

inline int Lcm(int a, int b) {
    return a * b / Gcd(a, b);
}

set<int> bad_node[MAX_L];
set<pii> bad_edge[MAX_L];
//queue<pii> q;//[MAX_L];
//bitset<MAX_N> visited[MAX_L];
//int dist[MAX_N][MAX_L];
int cycle[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vvi graph(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) cycle[i] = 1;
    int k;
    cin >> k;
    vi len(k);
    vvi path(k);
    for (int j = 0; j < k; j++) {
        cin >> len[j];
        path[j].resize(len[j] + 1);
        for (int i = 0; i < len[j]; i++) {
            cin >> path[j][i];
            cycle[path[j][i]] = len[j];
        }
        path[j][len[j]] = path[j][0];
        for (int i = 1; i <= len[j]; i++) {
            bad_node[i % len[j]].insert(path[j][i]);
            bad_edge[i % len[j]].insert({min(path[j][i], path[j][i - 1]), max(path[j][i], path[j][i - 1])});
        }
    }
    bitset<MAX_N> vis;
    vvb visited(n + 1);
    for (int i = 1; i <= n; i++) {
        if (cycle[i] == 1) {
            vis[i] = true;
            for (int neighbor : graph[i]) {
                if (!vis[neighbor]) cycle[i] = Lcm(cycle[i], cycle[neighbor]);
            }
        }
        visited[i].resize(cycle[i]);
//        for (int j = 0; j < cycle[i]; j++) dist[i][j] = infinity;
    }
//    priority_queue<pii, vii, greater<pii>> pq;
    queue<pii> pq;
    pq.push({1, 0});
    while (!pq.empty()) {
        auto [node, d] = pq.front();
        pq.pop();
//        if (visited[node][d % cycle[node]]) continue;
//        visited[node][d % cycle[node]] = true;
        if (node == n) {
            cout << d << '\n';
            return 0;
        }
        if (!bad_node[(d + 1) % cycle[node]].count(node)) {
            if (!visited[node][(d + 1) % cycle[node]]) {
                pq.push({node, d + 1});
                visited[node][(d + 1) % cycle[node]] = true;
            }
//            if (d + 1 < dist[node][(d + 1) % cycle[node]]) {
//                dist[node][(d + 1) % cycle[node]] = d + 1;
//                pq.push({node, d + 1});
//            }
        }
        for (int neighbor : graph[node]) {
            if (!bad_node[(d + 1) % cycle[neighbor]].count(neighbor)) {
                if (!bad_edge[(d + 1) % cycle[neighbor]].count({min(node, neighbor), max(node, neighbor)})) {
                    if (!visited[neighbor][(d + 1) % cycle[neighbor]]) {
                        pq.push({neighbor, d + 1});
                        visited[neighbor][(d + 1) % cycle[neighbor]] = true;
                    }
//                    if (d + 1 < dist[neighbor][(d + 1) % cycle[neighbor]]) {
//                        dist[node][(d + 1) % cycle[neighbor]] = d + 1;
//                        pq.push({neighbor, d + 1});
//                    }
                }
            }
        }
    }
    cout << "impossible\n";
    return 0;
}
//6 6
//1 2
//2 3
//3 4
//4 5
//5 6
//2 4
//1
//3 2 3 4

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29396 KB Output is correct
2 Correct 86 ms 41408 KB Output is correct
3 Correct 92 ms 40228 KB Output is correct
4 Correct 176 ms 40380 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 94 ms 40160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29396 KB Output is correct
2 Correct 96 ms 41468 KB Output is correct
3 Correct 97 ms 40192 KB Output is correct
4 Correct 173 ms 40480 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 81 ms 40244 KB Output is correct
7 Correct 87 ms 40220 KB Output is correct
8 Correct 89 ms 40260 KB Output is correct
9 Correct 109 ms 40272 KB Output is correct
10 Correct 469 ms 40548 KB Output is correct
11 Correct 1096 ms 41636 KB Output is correct
12 Correct 90 ms 40224 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29396 KB Output is correct
2 Correct 96 ms 41468 KB Output is correct
3 Correct 97 ms 40192 KB Output is correct
4 Correct 173 ms 40480 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 81 ms 40244 KB Output is correct
7 Correct 87 ms 40220 KB Output is correct
8 Correct 89 ms 40260 KB Output is correct
9 Correct 109 ms 40272 KB Output is correct
10 Correct 469 ms 40548 KB Output is correct
11 Correct 1096 ms 41636 KB Output is correct
12 Correct 90 ms 40224 KB Output is correct
13 Correct 36 ms 29456 KB Output is correct
14 Correct 109 ms 41340 KB Output is correct
15 Correct 80 ms 40244 KB Output is correct
16 Correct 161 ms 40512 KB Output is correct
17 Correct 19 ms 28512 KB Output is correct
18 Correct 88 ms 40296 KB Output is correct
19 Correct 92 ms 40240 KB Output is correct
20 Correct 102 ms 40168 KB Output is correct
21 Correct 107 ms 40268 KB Output is correct
22 Correct 434 ms 40528 KB Output is correct
23 Correct 1090 ms 41712 KB Output is correct
24 Correct 92 ms 40160 KB Output is correct
25 Correct 1664 ms 92616 KB Output is correct
26 Correct 1666 ms 135096 KB Output is correct
27 Correct 1641 ms 131244 KB Output is correct
28 Correct 1393 ms 135408 KB Output is correct
29 Execution timed out 6087 ms 127916 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29396 KB Output is correct
2 Correct 96 ms 41468 KB Output is correct
3 Correct 97 ms 40192 KB Output is correct
4 Correct 173 ms 40480 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 81 ms 40244 KB Output is correct
7 Correct 87 ms 40220 KB Output is correct
8 Correct 89 ms 40260 KB Output is correct
9 Correct 109 ms 40272 KB Output is correct
10 Correct 469 ms 40548 KB Output is correct
11 Correct 1096 ms 41636 KB Output is correct
12 Correct 90 ms 40224 KB Output is correct
13 Correct 36 ms 29456 KB Output is correct
14 Correct 109 ms 41340 KB Output is correct
15 Correct 80 ms 40244 KB Output is correct
16 Correct 161 ms 40512 KB Output is correct
17 Correct 19 ms 28512 KB Output is correct
18 Correct 88 ms 40296 KB Output is correct
19 Correct 92 ms 40240 KB Output is correct
20 Correct 102 ms 40168 KB Output is correct
21 Correct 107 ms 40268 KB Output is correct
22 Correct 434 ms 40528 KB Output is correct
23 Correct 1090 ms 41712 KB Output is correct
24 Correct 92 ms 40160 KB Output is correct
25 Correct 1664 ms 92616 KB Output is correct
26 Correct 1666 ms 135096 KB Output is correct
27 Correct 1641 ms 131244 KB Output is correct
28 Correct 1393 ms 135408 KB Output is correct
29 Execution timed out 6087 ms 127916 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29396 KB Output is correct
2 Correct 86 ms 41408 KB Output is correct
3 Correct 92 ms 40228 KB Output is correct
4 Correct 176 ms 40380 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 94 ms 40160 KB Output is correct
7 Correct 28 ms 29396 KB Output is correct
8 Correct 96 ms 41468 KB Output is correct
9 Correct 97 ms 40192 KB Output is correct
10 Correct 173 ms 40480 KB Output is correct
11 Correct 14 ms 28500 KB Output is correct
12 Correct 81 ms 40244 KB Output is correct
13 Correct 87 ms 40220 KB Output is correct
14 Correct 89 ms 40260 KB Output is correct
15 Correct 109 ms 40272 KB Output is correct
16 Correct 469 ms 40548 KB Output is correct
17 Correct 1096 ms 41636 KB Output is correct
18 Correct 90 ms 40224 KB Output is correct
19 Correct 13 ms 28440 KB Output is correct
20 Correct 13 ms 28440 KB Output is correct
21 Correct 13 ms 28500 KB Output is correct
22 Correct 28 ms 29372 KB Output is correct
23 Correct 93 ms 41364 KB Output is correct
24 Correct 104 ms 40140 KB Output is correct
25 Correct 159 ms 40260 KB Output is correct
26 Correct 15 ms 28468 KB Output is correct
27 Correct 79 ms 40188 KB Output is correct
28 Correct 94 ms 40188 KB Output is correct
29 Correct 79 ms 40140 KB Output is correct
30 Correct 89 ms 40144 KB Output is correct
31 Correct 442 ms 40552 KB Output is correct
32 Correct 1075 ms 41692 KB Output is correct
33 Correct 87 ms 40208 KB Output is correct
34 Correct 2209 ms 94140 KB Output is correct
35 Correct 1956 ms 127944 KB Output is correct
36 Correct 2021 ms 127888 KB Output is correct
37 Incorrect 1863 ms 133968 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29396 KB Output is correct
2 Correct 86 ms 41408 KB Output is correct
3 Correct 92 ms 40228 KB Output is correct
4 Correct 176 ms 40380 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 94 ms 40160 KB Output is correct
7 Correct 28 ms 29396 KB Output is correct
8 Correct 96 ms 41468 KB Output is correct
9 Correct 97 ms 40192 KB Output is correct
10 Correct 173 ms 40480 KB Output is correct
11 Correct 14 ms 28500 KB Output is correct
12 Correct 81 ms 40244 KB Output is correct
13 Correct 87 ms 40220 KB Output is correct
14 Correct 89 ms 40260 KB Output is correct
15 Correct 109 ms 40272 KB Output is correct
16 Correct 469 ms 40548 KB Output is correct
17 Correct 1096 ms 41636 KB Output is correct
18 Correct 90 ms 40224 KB Output is correct
19 Correct 36 ms 29456 KB Output is correct
20 Correct 109 ms 41340 KB Output is correct
21 Correct 80 ms 40244 KB Output is correct
22 Correct 161 ms 40512 KB Output is correct
23 Correct 19 ms 28512 KB Output is correct
24 Correct 88 ms 40296 KB Output is correct
25 Correct 92 ms 40240 KB Output is correct
26 Correct 102 ms 40168 KB Output is correct
27 Correct 107 ms 40268 KB Output is correct
28 Correct 434 ms 40528 KB Output is correct
29 Correct 1090 ms 41712 KB Output is correct
30 Correct 92 ms 40160 KB Output is correct
31 Correct 1664 ms 92616 KB Output is correct
32 Correct 1666 ms 135096 KB Output is correct
33 Correct 1641 ms 131244 KB Output is correct
34 Correct 1393 ms 135408 KB Output is correct
35 Execution timed out 6087 ms 127916 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29396 KB Output is correct
2 Correct 86 ms 41408 KB Output is correct
3 Correct 92 ms 40228 KB Output is correct
4 Correct 176 ms 40380 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 94 ms 40160 KB Output is correct
7 Correct 28 ms 29396 KB Output is correct
8 Correct 96 ms 41468 KB Output is correct
9 Correct 97 ms 40192 KB Output is correct
10 Correct 173 ms 40480 KB Output is correct
11 Correct 14 ms 28500 KB Output is correct
12 Correct 81 ms 40244 KB Output is correct
13 Correct 87 ms 40220 KB Output is correct
14 Correct 89 ms 40260 KB Output is correct
15 Correct 109 ms 40272 KB Output is correct
16 Correct 469 ms 40548 KB Output is correct
17 Correct 1096 ms 41636 KB Output is correct
18 Correct 90 ms 40224 KB Output is correct
19 Correct 36 ms 29456 KB Output is correct
20 Correct 109 ms 41340 KB Output is correct
21 Correct 80 ms 40244 KB Output is correct
22 Correct 161 ms 40512 KB Output is correct
23 Correct 19 ms 28512 KB Output is correct
24 Correct 88 ms 40296 KB Output is correct
25 Correct 92 ms 40240 KB Output is correct
26 Correct 102 ms 40168 KB Output is correct
27 Correct 107 ms 40268 KB Output is correct
28 Correct 434 ms 40528 KB Output is correct
29 Correct 1090 ms 41712 KB Output is correct
30 Correct 92 ms 40160 KB Output is correct
31 Correct 1664 ms 92616 KB Output is correct
32 Correct 1666 ms 135096 KB Output is correct
33 Correct 1641 ms 131244 KB Output is correct
34 Correct 1393 ms 135408 KB Output is correct
35 Execution timed out 6087 ms 127916 KB Time limit exceeded
36 Halted 0 ms 0 KB -