oj.uz

Submission #540481

# Submission time Handle Problem Language Result Execution time Memory
540481 2022-03-20T13:37:23 Z elazarkoren From Hacks to Snitches (BOI21_watchmen) C++17
5 / 100
 576 ms 377336 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;

const int MAX_N = 1e5 + 5;
const int MAX_L = 500;
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;
    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]);
            }
        }
        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[d % cycle[node]][node]) continue;
        visited[d % cycle[node]][node] = true;
        if (node == n) {
            cout << d << '\n';
            return 0;
        }
        if (!bad_node[(d + 1) % cycle[node]].count(node)) {
            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 (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 14 ms 2644 KB Output is correct
2 Correct 168 ms 203428 KB Output is correct
3 Correct 169 ms 183412 KB Output is correct
4 Correct 308 ms 183820 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 164 ms 183448 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2772 KB Output is correct
2 Correct 178 ms 203780 KB Output is correct
3 Correct 165 ms 183736 KB Output is correct
4 Correct 304 ms 183884 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 154 ms 183444 KB Output is correct
7 Correct 170 ms 182648 KB Output is correct
8 Correct 155 ms 183152 KB Output is correct
9 Correct 171 ms 183436 KB Output is correct
10 Runtime error 576 ms 377336 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2772 KB Output is correct
2 Correct 178 ms 203780 KB Output is correct
3 Correct 165 ms 183736 KB Output is correct
4 Correct 304 ms 183884 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 154 ms 183444 KB Output is correct
7 Correct 170 ms 182648 KB Output is correct
8 Correct 155 ms 183152 KB Output is correct
9 Correct 171 ms 183436 KB Output is correct
10 Runtime error 576 ms 377336 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2772 KB Output is correct
2 Correct 178 ms 203780 KB Output is correct
3 Correct 165 ms 183736 KB Output is correct
4 Correct 304 ms 183884 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 154 ms 183444 KB Output is correct
7 Correct 170 ms 182648 KB Output is correct
8 Correct 155 ms 183152 KB Output is correct
9 Correct 171 ms 183436 KB Output is correct
10 Runtime error 576 ms 377336 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2644 KB Output is correct
2 Correct 168 ms 203428 KB Output is correct
3 Correct 169 ms 183412 KB Output is correct
4 Correct 308 ms 183820 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 164 ms 183448 KB Output is correct
7 Correct 16 ms 2772 KB Output is correct
8 Correct 178 ms 203780 KB Output is correct
9 Correct 165 ms 183736 KB Output is correct
10 Correct 304 ms 183884 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 154 ms 183444 KB Output is correct
13 Correct 170 ms 182648 KB Output is correct
14 Correct 155 ms 183152 KB Output is correct
15 Correct 171 ms 183436 KB Output is correct
16 Runtime error 576 ms 377336 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2644 KB Output is correct
2 Correct 168 ms 203428 KB Output is correct
3 Correct 169 ms 183412 KB Output is correct
4 Correct 308 ms 183820 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 164 ms 183448 KB Output is correct
7 Correct 16 ms 2772 KB Output is correct
8 Correct 178 ms 203780 KB Output is correct
9 Correct 165 ms 183736 KB Output is correct
10 Correct 304 ms 183884 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 154 ms 183444 KB Output is correct
13 Correct 170 ms 182648 KB Output is correct
14 Correct 155 ms 183152 KB Output is correct
15 Correct 171 ms 183436 KB Output is correct
16 Runtime error 576 ms 377336 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2644 KB Output is correct
2 Correct 168 ms 203428 KB Output is correct
3 Correct 169 ms 183412 KB Output is correct
4 Correct 308 ms 183820 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 164 ms 183448 KB Output is correct
7 Correct 16 ms 2772 KB Output is correct
8 Correct 178 ms 203780 KB Output is correct
9 Correct 165 ms 183736 KB Output is correct
10 Correct 304 ms 183884 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 154 ms 183444 KB Output is correct
13 Correct 170 ms 182648 KB Output is correct
14 Correct 155 ms 183152 KB Output is correct
15 Correct 171 ms 183436 KB Output is correct
16 Runtime error 576 ms 377336 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -