oj.uz

Submission #540480

# Submission time Handle Problem Language Result Execution time Memory
540480 2022-03-20T13:37:23 Z elazarkoren From Hacks to Snitches (BOI21_watchmen) C++17
5 / 100
 574 ms 377064 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 16 ms 2676 KB Output is correct
2 Correct 164 ms 203468 KB Output is correct
3 Correct 174 ms 183720 KB Output is correct
4 Correct 301 ms 184104 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 164 ms 183720 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2644 KB Output is correct
2 Correct 183 ms 203464 KB Output is correct
3 Correct 161 ms 183376 KB Output is correct
4 Correct 306 ms 183968 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 151 ms 183728 KB Output is correct
7 Correct 162 ms 182928 KB Output is correct
8 Correct 155 ms 182764 KB Output is correct
9 Correct 178 ms 182196 KB Output is correct
10 Runtime error 574 ms 377064 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 2644 KB Output is correct
2 Correct 183 ms 203464 KB Output is correct
3 Correct 161 ms 183376 KB Output is correct
4 Correct 306 ms 183968 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 151 ms 183728 KB Output is correct
7 Correct 162 ms 182928 KB Output is correct
8 Correct 155 ms 182764 KB Output is correct
9 Correct 178 ms 182196 KB Output is correct
10 Runtime error 574 ms 377064 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 2644 KB Output is correct
2 Correct 183 ms 203464 KB Output is correct
3 Correct 161 ms 183376 KB Output is correct
4 Correct 306 ms 183968 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 151 ms 183728 KB Output is correct
7 Correct 162 ms 182928 KB Output is correct
8 Correct 155 ms 182764 KB Output is correct
9 Correct 178 ms 182196 KB Output is correct
10 Runtime error 574 ms 377064 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 16 ms 2676 KB Output is correct
2 Correct 164 ms 203468 KB Output is correct
3 Correct 174 ms 183720 KB Output is correct
4 Correct 301 ms 184104 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 164 ms 183720 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 183 ms 203464 KB Output is correct
9 Correct 161 ms 183376 KB Output is correct
10 Correct 306 ms 183968 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 151 ms 183728 KB Output is correct
13 Correct 162 ms 182928 KB Output is correct
14 Correct 155 ms 182764 KB Output is correct
15 Correct 178 ms 182196 KB Output is correct
16 Runtime error 574 ms 377064 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 16 ms 2676 KB Output is correct
2 Correct 164 ms 203468 KB Output is correct
3 Correct 174 ms 183720 KB Output is correct
4 Correct 301 ms 184104 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 164 ms 183720 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 183 ms 203464 KB Output is correct
9 Correct 161 ms 183376 KB Output is correct
10 Correct 306 ms 183968 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 151 ms 183728 KB Output is correct
13 Correct 162 ms 182928 KB Output is correct
14 Correct 155 ms 182764 KB Output is correct
15 Correct 178 ms 182196 KB Output is correct
16 Runtime error 574 ms 377064 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 16 ms 2676 KB Output is correct
2 Correct 164 ms 203468 KB Output is correct
3 Correct 174 ms 183720 KB Output is correct
4 Correct 301 ms 184104 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 164 ms 183720 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 183 ms 203464 KB Output is correct
9 Correct 161 ms 183376 KB Output is correct
10 Correct 306 ms 183968 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 151 ms 183728 KB Output is correct
13 Correct 162 ms 182928 KB Output is correct
14 Correct 155 ms 182764 KB Output is correct
15 Correct 178 ms 182196 KB Output is correct
16 Runtime error 574 ms 377064 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -