oj.uz

Submission #417365

# Submission time Handle Problem Language Result Execution time Memory
417365 2021-06-03T15:36:11 Z keko37 From Hacks to Snitches (BOI21_watchmen) C++14
40 / 100
 6000 ms 132912 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 250005;
const llint INF = 1000000000000000000LL;

int n, m, k;
int d[MAXN], ost[MAXN], koji[MAXN], special[MAXN];
llint best[MAXN], dist[3005][3005];
bool bio[3005][3005];
vector <pi> edges;

bool watched[MAXN];
vector <int> good, bad, sus_good[MAXN], sus_bad[MAXN];

void ispis () {
    cout << "good" << endl;
    for (auto x : good) {
        cout << x << ": ";
        for (auto sus : sus_good[x]) cout << sus << " ";
        cout << "| ";
        for (auto sus : sus_bad[x]) cout << sus << " ";
        cout << endl;
    }
    cout << "bad" << endl;
    for (auto x : bad) {
        cout << x << ": ";
        for (auto sus : sus_good[x]) cout << sus << " ";
        cout << "| ";
        for (auto sus : sus_bad[x]) cout << sus << " ";
        cout << endl;
    }
}

void build () {
    for (int i = 1; i <= n; i++) {
        if (watched[i]) bad.push_back(i); else good.push_back(i);
    }
    for (int i = 0; i < bad.size(); i++) {
        koji[bad[i]] = i;
    }
    for (auto pp : edges) {
        int a = pp.first, b = pp.second;
        if (watched[b]) sus_bad[a].push_back(b); else sus_good[a].push_back(b);
        if (watched[a]) sus_bad[b].push_back(a); else sus_good[b].push_back(a);
    }
}

priority_queue < pair <llint, pi> > pq;

void dijkstra () {
    for (int i = 1; i <= n; i++) {
        best[i] = INF;
    }
    for (int i = 0; i < bad.size(); i++) {
        int node = bad[i];
        for (int j = 0; j < d[node]; j++) {
            dist[i][j] = INF;
        }
    }
    best[1] = 0;
    pq.push({0, {-1, 1}});

    while (!pq.empty()) {
        llint pq_dist = -pq.top().first;
        int jen = pq.top().second.first;
        int dva = pq.top().second.second;
        pq.pop();
        int node;
        if (jen == -1) {
            node = dva;
            if (pq_dist > best[node]) continue;
        } else {
            node = bad[jen];
            if (pq_dist > dist[jen][dva]) continue;
        }
        if (!watched[node]) {
            for (auto sus : sus_good[node]) {
                llint novi = best[node] + 1;
                if (novi < best[sus]) {
                    best[sus] = novi;
                    pq.push({-novi, {-1, sus}});
                }
            }
            for (auto sus : sus_bad[node]) {
                llint novi = best[node] + 1;
                int curr_ost = novi % d[sus];
                if (bio[koji[sus]][curr_ost]) continue;
                bio[koji[sus]][curr_ost] = 1;
                for (int i = 0; i < d[sus]; i++) {
                    curr_ost = novi % d[sus];
                    if (curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
                        dist[koji[sus]][curr_ost] = novi;
                        pq.push({-novi, {koji[sus], curr_ost}});
                    }
                    novi++;
                }
            }
        } else {
            if (best[node] == INF) {
                best[node] = pq_dist;
                for (auto sus : sus_good[node]) {
                    llint novi = best[node] + 1;
                    if (novi < best[sus]) {
                        best[sus] = novi;
                        pq.push({-novi, {-1, sus}});
                    }
                }
            }
            for (auto sus : sus_bad[node]) {
                if (sus == special[node]) continue;
                llint novi = pq_dist + 1;
                for (int i = 0; i < d[sus]; i++) {
                    int curr_ost = novi % d[sus];
                    if (curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
                        dist[koji[sus]][curr_ost] = novi;
                        pq.push({-novi, {koji[sus], curr_ost}});
                    }
                    novi += d[node];
                    if (d[node] == 2) break;
                }
            }

            int sus = special[node];
            llint novi = pq_dist + 1;
            int curr_ost = novi % d[node];
            if (curr_ost != ost[node] && curr_ost != ost[sus] && novi < dist[koji[sus]][curr_ost]) {
                dist[koji[sus]][curr_ost] = novi;
                pq.push({-novi, {koji[sus], curr_ost}});
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({a, b});
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int len;
        cin >> len;
        vector <int> tmp;
        for (int j = 0; j < len; j++) {
            int node;
            cin >> node;
            tmp.push_back(node);
            watched[node] = 1;
            d[node] = len;
            ost[node] = j;
        }
        for (int i = 1; i < tmp.size(); i++) {
            special[tmp[i]] = tmp[i - 1];
        }
        special[tmp[0]] = tmp.back();
    }
    build();
    dijkstra();
    if (best[n] == INF) cout << "impossible"; else cout << best[n];
    return 0;
}

Compilation message

watchmen.cpp: In function 'void build()':
watchmen.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < bad.size(); i++) {
      |                     ~~^~~~~~~~~~~~
watchmen.cpp: In function 'void dijkstra()':
watchmen.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < bad.size(); i++) {
      |                     ~~^~~~~~~~~~~~
watchmen.cpp: In function 'int main()':
watchmen.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 1; i < tmp.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 15392 KB Output is correct
2 Correct 82 ms 18908 KB Output is correct
3 Correct 84 ms 20540 KB Output is correct
4 Correct 1622 ms 21008 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 84 ms 20484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 15380 KB Output is correct
2 Correct 83 ms 19004 KB Output is correct
3 Correct 89 ms 20532 KB Output is correct
4 Correct 1582 ms 21260 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 86 ms 20536 KB Output is correct
7 Correct 72 ms 19888 KB Output is correct
8 Correct 65 ms 20160 KB Output is correct
9 Correct 60 ms 19816 KB Output is correct
10 Correct 227 ms 20604 KB Output is correct
11 Correct 78 ms 20368 KB Output is correct
12 Correct 70 ms 20156 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 15380 KB Output is correct
2 Correct 83 ms 19004 KB Output is correct
3 Correct 89 ms 20532 KB Output is correct
4 Correct 1582 ms 21260 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 86 ms 20536 KB Output is correct
7 Correct 72 ms 19888 KB Output is correct
8 Correct 65 ms 20160 KB Output is correct
9 Correct 60 ms 19816 KB Output is correct
10 Correct 227 ms 20604 KB Output is correct
11 Correct 78 ms 20368 KB Output is correct
12 Correct 70 ms 20156 KB Output is correct
13 Correct 1527 ms 15968 KB Output is correct
14 Correct 85 ms 20108 KB Output is correct
15 Correct 99 ms 20504 KB Output is correct
16 Correct 1577 ms 21000 KB Output is correct
17 Correct 21 ms 12748 KB Output is correct
18 Correct 85 ms 20448 KB Output is correct
19 Correct 72 ms 19876 KB Output is correct
20 Correct 66 ms 20048 KB Output is correct
21 Correct 64 ms 19724 KB Output is correct
22 Correct 226 ms 20672 KB Output is correct
23 Correct 90 ms 20524 KB Output is correct
24 Correct 72 ms 20156 KB Output is correct
25 Correct 1492 ms 125432 KB Output is correct
26 Correct 1464 ms 132912 KB Output is correct
27 Correct 1347 ms 127228 KB Output is correct
28 Correct 1144 ms 129648 KB Output is correct
29 Execution timed out 6051 ms 126804 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 15380 KB Output is correct
2 Correct 83 ms 19004 KB Output is correct
3 Correct 89 ms 20532 KB Output is correct
4 Correct 1582 ms 21260 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 86 ms 20536 KB Output is correct
7 Correct 72 ms 19888 KB Output is correct
8 Correct 65 ms 20160 KB Output is correct
9 Correct 60 ms 19816 KB Output is correct
10 Correct 227 ms 20604 KB Output is correct
11 Correct 78 ms 20368 KB Output is correct
12 Correct 70 ms 20156 KB Output is correct
13 Correct 1527 ms 15968 KB Output is correct
14 Correct 85 ms 20108 KB Output is correct
15 Correct 99 ms 20504 KB Output is correct
16 Correct 1577 ms 21000 KB Output is correct
17 Correct 21 ms 12748 KB Output is correct
18 Correct 85 ms 20448 KB Output is correct
19 Correct 72 ms 19876 KB Output is correct
20 Correct 66 ms 20048 KB Output is correct
21 Correct 64 ms 19724 KB Output is correct
22 Correct 226 ms 20672 KB Output is correct
23 Correct 90 ms 20524 KB Output is correct
24 Correct 72 ms 20156 KB Output is correct
25 Correct 1492 ms 125432 KB Output is correct
26 Correct 1464 ms 132912 KB Output is correct
27 Correct 1347 ms 127228 KB Output is correct
28 Correct 1144 ms 129648 KB Output is correct
29 Execution timed out 6051 ms 126804 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 15392 KB Output is correct
2 Correct 82 ms 18908 KB Output is correct
3 Correct 84 ms 20540 KB Output is correct
4 Correct 1622 ms 21008 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 84 ms 20484 KB Output is correct
7 Correct 1524 ms 15380 KB Output is correct
8 Correct 83 ms 19004 KB Output is correct
9 Correct 89 ms 20532 KB Output is correct
10 Correct 1582 ms 21260 KB Output is correct
11 Correct 21 ms 12748 KB Output is correct
12 Correct 86 ms 20536 KB Output is correct
13 Correct 72 ms 19888 KB Output is correct
14 Correct 65 ms 20160 KB Output is correct
15 Correct 60 ms 19816 KB Output is correct
16 Correct 227 ms 20604 KB Output is correct
17 Correct 78 ms 20368 KB Output is correct
18 Correct 70 ms 20156 KB Output is correct
19 Correct 7 ms 12108 KB Output is correct
20 Correct 7 ms 12108 KB Output is correct
21 Correct 7 ms 12040 KB Output is correct
22 Correct 1528 ms 16004 KB Output is correct
23 Correct 94 ms 20160 KB Output is correct
24 Correct 104 ms 20576 KB Output is correct
25 Correct 1601 ms 21044 KB Output is correct
26 Correct 22 ms 12620 KB Output is correct
27 Correct 92 ms 20536 KB Output is correct
28 Correct 76 ms 19812 KB Output is correct
29 Correct 70 ms 20108 KB Output is correct
30 Correct 65 ms 19768 KB Output is correct
31 Correct 235 ms 20672 KB Output is correct
32 Correct 83 ms 20480 KB Output is correct
33 Correct 88 ms 20160 KB Output is correct
34 Correct 1677 ms 127592 KB Output is correct
35 Correct 1746 ms 122900 KB Output is correct
36 Correct 1741 ms 122852 KB Output is correct
37 Correct 1580 ms 127772 KB Output is correct
38 Correct 1679 ms 124336 KB Output is correct
39 Correct 2518 ms 126044 KB Output is correct
40 Correct 1909 ms 126316 KB Output is correct
41 Correct 1654 ms 125936 KB Output is correct
42 Correct 1657 ms 124176 KB Output is correct
43 Correct 1771 ms 131004 KB Output is correct
44 Correct 1823 ms 131460 KB Output is correct
45 Correct 1740 ms 124800 KB Output is correct
46 Correct 1584 ms 124176 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 15392 KB Output is correct
2 Correct 82 ms 18908 KB Output is correct
3 Correct 84 ms 20540 KB Output is correct
4 Correct 1622 ms 21008 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 84 ms 20484 KB Output is correct
7 Correct 1524 ms 15380 KB Output is correct
8 Correct 83 ms 19004 KB Output is correct
9 Correct 89 ms 20532 KB Output is correct
10 Correct 1582 ms 21260 KB Output is correct
11 Correct 21 ms 12748 KB Output is correct
12 Correct 86 ms 20536 KB Output is correct
13 Correct 72 ms 19888 KB Output is correct
14 Correct 65 ms 20160 KB Output is correct
15 Correct 60 ms 19816 KB Output is correct
16 Correct 227 ms 20604 KB Output is correct
17 Correct 78 ms 20368 KB Output is correct
18 Correct 70 ms 20156 KB Output is correct
19 Correct 1527 ms 15968 KB Output is correct
20 Correct 85 ms 20108 KB Output is correct
21 Correct 99 ms 20504 KB Output is correct
22 Correct 1577 ms 21000 KB Output is correct
23 Correct 21 ms 12748 KB Output is correct
24 Correct 85 ms 20448 KB Output is correct
25 Correct 72 ms 19876 KB Output is correct
26 Correct 66 ms 20048 KB Output is correct
27 Correct 64 ms 19724 KB Output is correct
28 Correct 226 ms 20672 KB Output is correct
29 Correct 90 ms 20524 KB Output is correct
30 Correct 72 ms 20156 KB Output is correct
31 Correct 1492 ms 125432 KB Output is correct
32 Correct 1464 ms 132912 KB Output is correct
33 Correct 1347 ms 127228 KB Output is correct
34 Correct 1144 ms 129648 KB Output is correct
35 Execution timed out 6051 ms 126804 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 15392 KB Output is correct
2 Correct 82 ms 18908 KB Output is correct
3 Correct 84 ms 20540 KB Output is correct
4 Correct 1622 ms 21008 KB Output is correct
5 Correct 21 ms 12748 KB Output is correct
6 Correct 84 ms 20484 KB Output is correct
7 Correct 1524 ms 15380 KB Output is correct
8 Correct 83 ms 19004 KB Output is correct
9 Correct 89 ms 20532 KB Output is correct
10 Correct 1582 ms 21260 KB Output is correct
11 Correct 21 ms 12748 KB Output is correct
12 Correct 86 ms 20536 KB Output is correct
13 Correct 72 ms 19888 KB Output is correct
14 Correct 65 ms 20160 KB Output is correct
15 Correct 60 ms 19816 KB Output is correct
16 Correct 227 ms 20604 KB Output is correct
17 Correct 78 ms 20368 KB Output is correct
18 Correct 70 ms 20156 KB Output is correct
19 Correct 1527 ms 15968 KB Output is correct
20 Correct 85 ms 20108 KB Output is correct
21 Correct 99 ms 20504 KB Output is correct
22 Correct 1577 ms 21000 KB Output is correct
23 Correct 21 ms 12748 KB Output is correct
24 Correct 85 ms 20448 KB Output is correct
25 Correct 72 ms 19876 KB Output is correct
26 Correct 66 ms 20048 KB Output is correct
27 Correct 64 ms 19724 KB Output is correct
28 Correct 226 ms 20672 KB Output is correct
29 Correct 90 ms 20524 KB Output is correct
30 Correct 72 ms 20156 KB Output is correct
31 Correct 1492 ms 125432 KB Output is correct
32 Correct 1464 ms 132912 KB Output is correct
33 Correct 1347 ms 127228 KB Output is correct
34 Correct 1144 ms 129648 KB Output is correct
35 Execution timed out 6051 ms 126804 KB Time limit exceeded
36 Halted 0 ms 0 KB -