oj.uz

Submission #751433

# Submission time Handle Problem Language Result Execution time Memory
751433 2023-05-31T14:53:37 Z lohacho From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 480460 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const int NS = 250004;

int n, m;
vector<int> way[NS];
vector<int> dp[NS];
int len[NS], fir[NS], col[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    int k;
    cin >> k;
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        for(int j = 0; j < x; ++j){
            int y;
            cin >> y;
            --y;
            dp[y] = vector<int>(x, (int)1e18);
            len[y] = x;
            col[y] = i + 1;
            fir[y] = j;
        }
    }

    for(int i = 0; i < n; ++i){
        if(!(int)dp[i].size()){
            dp[i] = {(int)1e18};
        }
    }

    priority_queue<vector<int>> pq;

    auto enq = [&](int x, int t){
        int md = (col[x] ? t % len[x] : 0);
        if((!col[x] || md != fir[x]) && t < dp[x][md]){
            pq.push({-t, x});
        }
    };

    auto gett = [&](int x, int t){
        if(t <= fir[x]) return fir[x];
        return ((t - fir[x] - 1) / len[x] + 1) * len[x] + fir[x];
    };

    enq(0, 0);
    while(!pq.empty()){
        int now = pq.top()[1];
        int nt = -pq.top()[0];
        pq.pop();

        int md = (col[now] ? nt % len[now] : 0);
        if(dp[now][md] == nt){
            continue;
        }
        if(now == n - 1){
            cout << nt << '\n';
            return 0;
        }
        //cout << now + 1 << ' ' << nt << endl;

        dp[now][md] = nt;
        enq(now, nt + 1);
        for(int i = 0; i < (int)way[now].size(); ++i){
            int nxt = way[now][i];
            if(!col[now] || !(col[now] == col[nxt] && fir[now] == (fir[nxt] + 1) % len[now] && fir[nxt] == nt % len[now])){
                enq(nxt, nt + 1);
            }
            if(!col[now] && col[nxt]){
                enq(nxt, gett(nxt, nt) + 1);
            }
            int f = 0;
            if(col[now] && col[nxt] && (col[now] != col[nxt] || (fir[now] == (fir[nxt] + 1) % len[now] && fir[nxt] == (fir[now] + 1) % len[nxt]))){
                int t2 = gett(nxt, nt);
                int t1 = gett(now, t2);
                if(t1 != t2){
                    enq(nxt, t2 + 1);
                    f = 1;
                }
                else{
                    int t3 = t1 + (len[now] * 2 - fir[now] + md) % len[now];
                    int t4 = gett(nxt, t3);
                    //enq(nxt, t3 + 1);
                    if(t3 != t4){
                        //enq(nxt, t4 + 1);
                    }
                }
            }

            if(!col[now] || !col[nxt] || f){
                swap(way[now][i], way[now].back());
                way[now].pop_back();
                --i;
            }
        }
    }

    cout << "impossible\n";
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14508 KB Output is correct
2 Correct 81 ms 20580 KB Output is correct
3 Correct 92 ms 20904 KB Output is correct
4 Correct 663 ms 21652 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 87 ms 20836 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14424 KB Output is correct
2 Correct 85 ms 20556 KB Output is correct
3 Correct 98 ms 20956 KB Output is correct
4 Correct 658 ms 21748 KB Output is correct
5 Correct 10 ms 12116 KB Output is correct
6 Correct 89 ms 20824 KB Output is correct
7 Correct 79 ms 20840 KB Output is correct
8 Correct 74 ms 20720 KB Output is correct
9 Correct 71 ms 20608 KB Output is correct
10 Correct 206 ms 21856 KB Output is correct
11 Correct 111 ms 21472 KB Output is correct
12 Correct 84 ms 20908 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14424 KB Output is correct
2 Correct 85 ms 20556 KB Output is correct
3 Correct 98 ms 20956 KB Output is correct
4 Correct 658 ms 21748 KB Output is correct
5 Correct 10 ms 12116 KB Output is correct
6 Correct 89 ms 20824 KB Output is correct
7 Correct 79 ms 20840 KB Output is correct
8 Correct 74 ms 20720 KB Output is correct
9 Correct 71 ms 20608 KB Output is correct
10 Correct 206 ms 21856 KB Output is correct
11 Correct 111 ms 21472 KB Output is correct
12 Correct 84 ms 20908 KB Output is correct
13 Correct 18 ms 14536 KB Output is correct
14 Correct 79 ms 20528 KB Output is correct
15 Correct 94 ms 20964 KB Output is correct
16 Correct 653 ms 21712 KB Output is correct
17 Correct 12 ms 12116 KB Output is correct
18 Correct 92 ms 20812 KB Output is correct
19 Correct 83 ms 20736 KB Output is correct
20 Correct 77 ms 20836 KB Output is correct
21 Correct 72 ms 20576 KB Output is correct
22 Correct 216 ms 21768 KB Output is correct
23 Correct 112 ms 21484 KB Output is correct
24 Correct 82 ms 20884 KB Output is correct
25 Correct 5568 ms 295172 KB Output is correct
26 Correct 5378 ms 239180 KB Output is correct
27 Correct 5416 ms 296592 KB Output is correct
28 Correct 4696 ms 304880 KB Output is correct
29 Execution timed out 6114 ms 480460 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14424 KB Output is correct
2 Correct 85 ms 20556 KB Output is correct
3 Correct 98 ms 20956 KB Output is correct
4 Correct 658 ms 21748 KB Output is correct
5 Correct 10 ms 12116 KB Output is correct
6 Correct 89 ms 20824 KB Output is correct
7 Correct 79 ms 20840 KB Output is correct
8 Correct 74 ms 20720 KB Output is correct
9 Correct 71 ms 20608 KB Output is correct
10 Correct 206 ms 21856 KB Output is correct
11 Correct 111 ms 21472 KB Output is correct
12 Correct 84 ms 20908 KB Output is correct
13 Correct 18 ms 14536 KB Output is correct
14 Correct 79 ms 20528 KB Output is correct
15 Correct 94 ms 20964 KB Output is correct
16 Correct 653 ms 21712 KB Output is correct
17 Correct 12 ms 12116 KB Output is correct
18 Correct 92 ms 20812 KB Output is correct
19 Correct 83 ms 20736 KB Output is correct
20 Correct 77 ms 20836 KB Output is correct
21 Correct 72 ms 20576 KB Output is correct
22 Correct 216 ms 21768 KB Output is correct
23 Correct 112 ms 21484 KB Output is correct
24 Correct 82 ms 20884 KB Output is correct
25 Correct 5568 ms 295172 KB Output is correct
26 Correct 5378 ms 239180 KB Output is correct
27 Correct 5416 ms 296592 KB Output is correct
28 Correct 4696 ms 304880 KB Output is correct
29 Execution timed out 6114 ms 480460 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14508 KB Output is correct
2 Correct 81 ms 20580 KB Output is correct
3 Correct 92 ms 20904 KB Output is correct
4 Correct 663 ms 21652 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 87 ms 20836 KB Output is correct
7 Correct 19 ms 14424 KB Output is correct
8 Correct 85 ms 20556 KB Output is correct
9 Correct 98 ms 20956 KB Output is correct
10 Correct 658 ms 21748 KB Output is correct
11 Correct 10 ms 12116 KB Output is correct
12 Correct 89 ms 20824 KB Output is correct
13 Correct 79 ms 20840 KB Output is correct
14 Correct 74 ms 20720 KB Output is correct
15 Correct 71 ms 20608 KB Output is correct
16 Correct 206 ms 21856 KB Output is correct
17 Correct 111 ms 21472 KB Output is correct
18 Correct 84 ms 20908 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 6 ms 12072 KB Output is correct
21 Correct 6 ms 12076 KB Output is correct
22 Correct 18 ms 14496 KB Output is correct
23 Correct 77 ms 20576 KB Output is correct
24 Correct 90 ms 20940 KB Output is correct
25 Correct 649 ms 21704 KB Output is correct
26 Correct 10 ms 12244 KB Output is correct
27 Correct 91 ms 20808 KB Output is correct
28 Correct 81 ms 20720 KB Output is correct
29 Correct 73 ms 20836 KB Output is correct
30 Correct 67 ms 20560 KB Output is correct
31 Correct 217 ms 21892 KB Output is correct
32 Correct 104 ms 21384 KB Output is correct
33 Correct 98 ms 20868 KB Output is correct
34 Correct 5723 ms 295220 KB Output is correct
35 Correct 5934 ms 288088 KB Output is correct
36 Execution timed out 6002 ms 287932 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14508 KB Output is correct
2 Correct 81 ms 20580 KB Output is correct
3 Correct 92 ms 20904 KB Output is correct
4 Correct 663 ms 21652 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 87 ms 20836 KB Output is correct
7 Correct 19 ms 14424 KB Output is correct
8 Correct 85 ms 20556 KB Output is correct
9 Correct 98 ms 20956 KB Output is correct
10 Correct 658 ms 21748 KB Output is correct
11 Correct 10 ms 12116 KB Output is correct
12 Correct 89 ms 20824 KB Output is correct
13 Correct 79 ms 20840 KB Output is correct
14 Correct 74 ms 20720 KB Output is correct
15 Correct 71 ms 20608 KB Output is correct
16 Correct 206 ms 21856 KB Output is correct
17 Correct 111 ms 21472 KB Output is correct
18 Correct 84 ms 20908 KB Output is correct
19 Correct 18 ms 14536 KB Output is correct
20 Correct 79 ms 20528 KB Output is correct
21 Correct 94 ms 20964 KB Output is correct
22 Correct 653 ms 21712 KB Output is correct
23 Correct 12 ms 12116 KB Output is correct
24 Correct 92 ms 20812 KB Output is correct
25 Correct 83 ms 20736 KB Output is correct
26 Correct 77 ms 20836 KB Output is correct
27 Correct 72 ms 20576 KB Output is correct
28 Correct 216 ms 21768 KB Output is correct
29 Correct 112 ms 21484 KB Output is correct
30 Correct 82 ms 20884 KB Output is correct
31 Correct 5568 ms 295172 KB Output is correct
32 Correct 5378 ms 239180 KB Output is correct
33 Correct 5416 ms 296592 KB Output is correct
34 Correct 4696 ms 304880 KB Output is correct
35 Execution timed out 6114 ms 480460 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14508 KB Output is correct
2 Correct 81 ms 20580 KB Output is correct
3 Correct 92 ms 20904 KB Output is correct
4 Correct 663 ms 21652 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 87 ms 20836 KB Output is correct
7 Correct 19 ms 14424 KB Output is correct
8 Correct 85 ms 20556 KB Output is correct
9 Correct 98 ms 20956 KB Output is correct
10 Correct 658 ms 21748 KB Output is correct
11 Correct 10 ms 12116 KB Output is correct
12 Correct 89 ms 20824 KB Output is correct
13 Correct 79 ms 20840 KB Output is correct
14 Correct 74 ms 20720 KB Output is correct
15 Correct 71 ms 20608 KB Output is correct
16 Correct 206 ms 21856 KB Output is correct
17 Correct 111 ms 21472 KB Output is correct
18 Correct 84 ms 20908 KB Output is correct
19 Correct 18 ms 14536 KB Output is correct
20 Correct 79 ms 20528 KB Output is correct
21 Correct 94 ms 20964 KB Output is correct
22 Correct 653 ms 21712 KB Output is correct
23 Correct 12 ms 12116 KB Output is correct
24 Correct 92 ms 20812 KB Output is correct
25 Correct 83 ms 20736 KB Output is correct
26 Correct 77 ms 20836 KB Output is correct
27 Correct 72 ms 20576 KB Output is correct
28 Correct 216 ms 21768 KB Output is correct
29 Correct 112 ms 21484 KB Output is correct
30 Correct 82 ms 20884 KB Output is correct
31 Correct 5568 ms 295172 KB Output is correct
32 Correct 5378 ms 239180 KB Output is correct
33 Correct 5416 ms 296592 KB Output is correct
34 Correct 4696 ms 304880 KB Output is correct
35 Execution timed out 6114 ms 480460 KB Time limit exceeded
36 Halted 0 ms 0 KB -