oj.uz

답안 #540482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540482 2022-03-20T13:38:41 Z elazarkoren From Hacks to Snitches (BOI21_watchmen) C++17
5 / 100
 883 ms 138468 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 = 5000;
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 (!visited[(d + 1) % cycle[node]][node]) {
                pq.push({node, d + 1});
            }
//            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[(d + 1) % cycle[neighbor]][neighbor]) {
                        pq.push({neighbor, d + 1});
                    }
//                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 47 ms 8684 KB Output is correct
3 Correct 51 ms 8092 KB Output is correct
4 Correct 143 ms 8568 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 48 ms 8028 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3028 KB Output is correct
2 Correct 51 ms 8516 KB Output is correct
3 Correct 48 ms 8012 KB Output is correct
4 Correct 153 ms 8668 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 46 ms 7988 KB Output is correct
7 Correct 46 ms 7188 KB Output is correct
8 Correct 49 ms 6988 KB Output is correct
9 Correct 55 ms 6680 KB Output is correct
10 Correct 384 ms 50772 KB Output is correct
11 Runtime error 883 ms 138468 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3028 KB Output is correct
2 Correct 51 ms 8516 KB Output is correct
3 Correct 48 ms 8012 KB Output is correct
4 Correct 153 ms 8668 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 46 ms 7988 KB Output is correct
7 Correct 46 ms 7188 KB Output is correct
8 Correct 49 ms 6988 KB Output is correct
9 Correct 55 ms 6680 KB Output is correct
10 Correct 384 ms 50772 KB Output is correct
11 Runtime error 883 ms 138468 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3028 KB Output is correct
2 Correct 51 ms 8516 KB Output is correct
3 Correct 48 ms 8012 KB Output is correct
4 Correct 153 ms 8668 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 46 ms 7988 KB Output is correct
7 Correct 46 ms 7188 KB Output is correct
8 Correct 49 ms 6988 KB Output is correct
9 Correct 55 ms 6680 KB Output is correct
10 Correct 384 ms 50772 KB Output is correct
11 Runtime error 883 ms 138468 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 47 ms 8684 KB Output is correct
3 Correct 51 ms 8092 KB Output is correct
4 Correct 143 ms 8568 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 48 ms 8028 KB Output is correct
7 Correct 16 ms 3028 KB Output is correct
8 Correct 51 ms 8516 KB Output is correct
9 Correct 48 ms 8012 KB Output is correct
10 Correct 153 ms 8668 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 46 ms 7988 KB Output is correct
13 Correct 46 ms 7188 KB Output is correct
14 Correct 49 ms 6988 KB Output is correct
15 Correct 55 ms 6680 KB Output is correct
16 Correct 384 ms 50772 KB Output is correct
17 Runtime error 883 ms 138468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 47 ms 8684 KB Output is correct
3 Correct 51 ms 8092 KB Output is correct
4 Correct 143 ms 8568 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 48 ms 8028 KB Output is correct
7 Correct 16 ms 3028 KB Output is correct
8 Correct 51 ms 8516 KB Output is correct
9 Correct 48 ms 8012 KB Output is correct
10 Correct 153 ms 8668 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 46 ms 7988 KB Output is correct
13 Correct 46 ms 7188 KB Output is correct
14 Correct 49 ms 6988 KB Output is correct
15 Correct 55 ms 6680 KB Output is correct
16 Correct 384 ms 50772 KB Output is correct
17 Runtime error 883 ms 138468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 47 ms 8684 KB Output is correct
3 Correct 51 ms 8092 KB Output is correct
4 Correct 143 ms 8568 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 48 ms 8028 KB Output is correct
7 Correct 16 ms 3028 KB Output is correct
8 Correct 51 ms 8516 KB Output is correct
9 Correct 48 ms 8012 KB Output is correct
10 Correct 153 ms 8668 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 46 ms 7988 KB Output is correct
13 Correct 46 ms 7188 KB Output is correct
14 Correct 49 ms 6988 KB Output is correct
15 Correct 55 ms 6680 KB Output is correct
16 Correct 384 ms 50772 KB Output is correct
17 Runtime error 883 ms 138468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -