oj.uz

Submission #751438

# Submission time Handle Problem Language Result Execution time Memory
751438 2023-05-31T15:00:09 Z lohacho From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 415532 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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)1e9);
            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)1e9};
        }
    }

    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(gett(now, t4) != 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 17 ms 13012 KB Output is correct
2 Correct 82 ms 19124 KB Output is correct
3 Correct 86 ms 19144 KB Output is correct
4 Correct 119 ms 21224 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 82 ms 19104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13012 KB Output is correct
2 Correct 86 ms 19196 KB Output is correct
3 Correct 123 ms 19184 KB Output is correct
4 Correct 110 ms 21208 KB Output is correct
5 Correct 9 ms 12072 KB Output is correct
6 Correct 94 ms 19148 KB Output is correct
7 Correct 84 ms 19148 KB Output is correct
8 Correct 91 ms 19188 KB Output is correct
9 Correct 73 ms 18988 KB Output is correct
10 Correct 97 ms 20300 KB Output is correct
11 Correct 92 ms 19824 KB Output is correct
12 Correct 105 ms 19276 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13012 KB Output is correct
2 Correct 86 ms 19196 KB Output is correct
3 Correct 123 ms 19184 KB Output is correct
4 Correct 110 ms 21208 KB Output is correct
5 Correct 9 ms 12072 KB Output is correct
6 Correct 94 ms 19148 KB Output is correct
7 Correct 84 ms 19148 KB Output is correct
8 Correct 91 ms 19188 KB Output is correct
9 Correct 73 ms 18988 KB Output is correct
10 Correct 97 ms 20300 KB Output is correct
11 Correct 92 ms 19824 KB Output is correct
12 Correct 105 ms 19276 KB Output is correct
13 Correct 18 ms 12960 KB Output is correct
14 Correct 78 ms 19144 KB Output is correct
15 Correct 86 ms 19208 KB Output is correct
16 Correct 121 ms 21200 KB Output is correct
17 Correct 9 ms 12124 KB Output is correct
18 Correct 99 ms 19096 KB Output is correct
19 Correct 79 ms 19148 KB Output is correct
20 Correct 74 ms 19196 KB Output is correct
21 Correct 66 ms 18984 KB Output is correct
22 Correct 93 ms 20184 KB Output is correct
23 Correct 87 ms 19788 KB Output is correct
24 Correct 97 ms 19180 KB Output is correct
25 Correct 5728 ms 224864 KB Output is correct
26 Correct 5511 ms 164680 KB Output is correct
27 Correct 5721 ms 225756 KB Output is correct
28 Correct 5293 ms 229940 KB Output is correct
29 Execution timed out 6054 ms 415532 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13012 KB Output is correct
2 Correct 86 ms 19196 KB Output is correct
3 Correct 123 ms 19184 KB Output is correct
4 Correct 110 ms 21208 KB Output is correct
5 Correct 9 ms 12072 KB Output is correct
6 Correct 94 ms 19148 KB Output is correct
7 Correct 84 ms 19148 KB Output is correct
8 Correct 91 ms 19188 KB Output is correct
9 Correct 73 ms 18988 KB Output is correct
10 Correct 97 ms 20300 KB Output is correct
11 Correct 92 ms 19824 KB Output is correct
12 Correct 105 ms 19276 KB Output is correct
13 Correct 18 ms 12960 KB Output is correct
14 Correct 78 ms 19144 KB Output is correct
15 Correct 86 ms 19208 KB Output is correct
16 Correct 121 ms 21200 KB Output is correct
17 Correct 9 ms 12124 KB Output is correct
18 Correct 99 ms 19096 KB Output is correct
19 Correct 79 ms 19148 KB Output is correct
20 Correct 74 ms 19196 KB Output is correct
21 Correct 66 ms 18984 KB Output is correct
22 Correct 93 ms 20184 KB Output is correct
23 Correct 87 ms 19788 KB Output is correct
24 Correct 97 ms 19180 KB Output is correct
25 Correct 5728 ms 224864 KB Output is correct
26 Correct 5511 ms 164680 KB Output is correct
27 Correct 5721 ms 225756 KB Output is correct
28 Correct 5293 ms 229940 KB Output is correct
29 Execution timed out 6054 ms 415532 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Correct 82 ms 19124 KB Output is correct
3 Correct 86 ms 19144 KB Output is correct
4 Correct 119 ms 21224 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 82 ms 19104 KB Output is correct
7 Correct 18 ms 13012 KB Output is correct
8 Correct 86 ms 19196 KB Output is correct
9 Correct 123 ms 19184 KB Output is correct
10 Correct 110 ms 21208 KB Output is correct
11 Correct 9 ms 12072 KB Output is correct
12 Correct 94 ms 19148 KB Output is correct
13 Correct 84 ms 19148 KB Output is correct
14 Correct 91 ms 19188 KB Output is correct
15 Correct 73 ms 18988 KB Output is correct
16 Correct 97 ms 20300 KB Output is correct
17 Correct 92 ms 19824 KB Output is correct
18 Correct 105 ms 19276 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Correct 7 ms 11988 KB Output is correct
21 Correct 7 ms 11988 KB Output is correct
22 Correct 19 ms 13012 KB Output is correct
23 Correct 94 ms 19096 KB Output is correct
24 Correct 78 ms 19116 KB Output is correct
25 Correct 118 ms 21220 KB Output is correct
26 Correct 9 ms 12116 KB Output is correct
27 Correct 150 ms 19152 KB Output is correct
28 Correct 79 ms 19180 KB Output is correct
29 Correct 91 ms 19096 KB Output is correct
30 Correct 78 ms 18984 KB Output is correct
31 Correct 110 ms 20292 KB Output is correct
32 Correct 107 ms 19860 KB Output is correct
33 Correct 103 ms 19064 KB Output is correct
34 Execution timed out 6040 ms 224496 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Correct 82 ms 19124 KB Output is correct
3 Correct 86 ms 19144 KB Output is correct
4 Correct 119 ms 21224 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 82 ms 19104 KB Output is correct
7 Correct 18 ms 13012 KB Output is correct
8 Correct 86 ms 19196 KB Output is correct
9 Correct 123 ms 19184 KB Output is correct
10 Correct 110 ms 21208 KB Output is correct
11 Correct 9 ms 12072 KB Output is correct
12 Correct 94 ms 19148 KB Output is correct
13 Correct 84 ms 19148 KB Output is correct
14 Correct 91 ms 19188 KB Output is correct
15 Correct 73 ms 18988 KB Output is correct
16 Correct 97 ms 20300 KB Output is correct
17 Correct 92 ms 19824 KB Output is correct
18 Correct 105 ms 19276 KB Output is correct
19 Correct 18 ms 12960 KB Output is correct
20 Correct 78 ms 19144 KB Output is correct
21 Correct 86 ms 19208 KB Output is correct
22 Correct 121 ms 21200 KB Output is correct
23 Correct 9 ms 12124 KB Output is correct
24 Correct 99 ms 19096 KB Output is correct
25 Correct 79 ms 19148 KB Output is correct
26 Correct 74 ms 19196 KB Output is correct
27 Correct 66 ms 18984 KB Output is correct
28 Correct 93 ms 20184 KB Output is correct
29 Correct 87 ms 19788 KB Output is correct
30 Correct 97 ms 19180 KB Output is correct
31 Correct 5728 ms 224864 KB Output is correct
32 Correct 5511 ms 164680 KB Output is correct
33 Correct 5721 ms 225756 KB Output is correct
34 Correct 5293 ms 229940 KB Output is correct
35 Execution timed out 6054 ms 415532 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Correct 82 ms 19124 KB Output is correct
3 Correct 86 ms 19144 KB Output is correct
4 Correct 119 ms 21224 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 82 ms 19104 KB Output is correct
7 Correct 18 ms 13012 KB Output is correct
8 Correct 86 ms 19196 KB Output is correct
9 Correct 123 ms 19184 KB Output is correct
10 Correct 110 ms 21208 KB Output is correct
11 Correct 9 ms 12072 KB Output is correct
12 Correct 94 ms 19148 KB Output is correct
13 Correct 84 ms 19148 KB Output is correct
14 Correct 91 ms 19188 KB Output is correct
15 Correct 73 ms 18988 KB Output is correct
16 Correct 97 ms 20300 KB Output is correct
17 Correct 92 ms 19824 KB Output is correct
18 Correct 105 ms 19276 KB Output is correct
19 Correct 18 ms 12960 KB Output is correct
20 Correct 78 ms 19144 KB Output is correct
21 Correct 86 ms 19208 KB Output is correct
22 Correct 121 ms 21200 KB Output is correct
23 Correct 9 ms 12124 KB Output is correct
24 Correct 99 ms 19096 KB Output is correct
25 Correct 79 ms 19148 KB Output is correct
26 Correct 74 ms 19196 KB Output is correct
27 Correct 66 ms 18984 KB Output is correct
28 Correct 93 ms 20184 KB Output is correct
29 Correct 87 ms 19788 KB Output is correct
30 Correct 97 ms 19180 KB Output is correct
31 Correct 5728 ms 224864 KB Output is correct
32 Correct 5511 ms 164680 KB Output is correct
33 Correct 5721 ms 225756 KB Output is correct
34 Correct 5293 ms 229940 KB Output is correct
35 Execution timed out 6054 ms 415532 KB Time limit exceeded
36 Halted 0 ms 0 KB -