oj.uz

Submission #404525

# Submission time Handle Problem Language Result Execution time Memory
404525 2021-05-14T14:16:52 Z doowey From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 98516 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 250110;
const int inf = (int)1e9;
vector<int> T[N];
int id[N];
int mod[N];
int ash[N];
vector<int> ord[N];
vector<int> dp[N];
vector<bool> vis[N];

struct item{
    int dist;
    int node;
    int inv;
    bool operator<(const item &q) const {
        return dist > q.dist;
    }
};

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int ui, vi;
    for(int i = 1; i <= m; i ++ ){
        cin >> ui >> vi;
        T[ui].push_back(vi);
        T[vi].push_back(ui);
    }
    int k;
    cin >> k;
    int sz;
    for(int iq = 1; iq <= k ; iq ++ ){
        cin >> sz;
        for(int j = 0; j < sz; j ++ ){
            cin >> ui;
            ash[ui] = j;
            mod[ui] = sz;
            id[ui] = iq;
            ord[iq].push_back(ui);
        }
    }
    for(int i = 1; i <= n; i ++ ){
        if(id[i] == 0){
            vis[i].resize(1, false);
            dp[i].resize(1, inf);
        }
        else{
            vis[i].resize(mod[i], false);
            dp[i].resize(mod[i], inf);
        }
    }
    priority_queue<item> pq;
    dp[1][0] = 0;
    pq.push({0, 1, 0});
    int node;
    int iinv;
    int dis;
    int ban0, ban1;
    int nex;
    while(!pq.empty()){
        dis = pq.top().dist;
        node = pq.top().node;
        iinv = pq.top().inv;
        pq.pop();
        if(vis[node][iinv]) continue;
        vis[node][iinv] = true;
        if(id[node] == 0){
            for(auto x : T[node]){
                if(id[x] == 0){
                    if(dp[x][0] > dis + 1){
                        dp[x][0] = dis + 1;
                        pq.push({dp[x][0], x, 0});
                    }
                }
                else{
                    for(int wait = 1; wait <= mod[x]; wait ++ ){
                        if(ord[id[x]][(wait + dis) % mod[x]] != x && dp[x][(wait + dis) % mod[x]] > dis + wait){
                            dp[x][(wait + dis) % mod[x]] = dis + wait;
                            pq.push({dp[x][(wait + dis) % mod[x]], x, (wait + dis) % mod[x]});
                        }
                    }
                }

            }
        }
        else{
            for(auto x : T[node]){
                if(id[x] == 0){
                    if(dp[x][0] > dis + 1){
                        dp[x][0] = dis + 1;
                        pq.push({dp[x][0], x, 0});
                    }
                }
                else if(id[x] == id[node]){
                    if((ash[x] + 1) % mod[x] != ash[node] && ord[id[x]][(dis + 1) % mod[x]] != x){
                        if(dp[x][(dis + 1) % mod[x]] > dis + 1){
                            dp[x][(dis + 1) % mod[x]] = dis + 1;
                            pq.push({dis + 1, x, (dis + 1) % mod[x]});
                        }
                    }
                }

            }

            ban0 = ord[id[node]][iinv];
            ban1 = ord[id[node]][(iinv + 1 + mod[node]) % mod[node]];

            nex = ord[id[node]][(ash[node] + 1) % mod[node]];
            if(dp[nex][(iinv + 1) % mod[nex]] > dis + 1){
                dp[nex][(iinv + 1) % mod[nex]] = dis + 1;
                pq.push({dis + 1, nex, (iinv + 1) % mod[nex]});
            }
            nex = ord[id[node]][(ash[node] - 1 + mod[node]) % mod[node]];
            if(nex != ban0 && nex != ban1 && dp[nex][(iinv + 1) % mod[nex]] > dis + 1){
                dp[nex][(iinv + 1) % mod[nex]] = dis + 1;
                pq.push({dis + 1, nex, (iinv + 1) % mod[nex]});
            }

        }
    }
    if(dp[n][0] < inf)
        cout << dp[n][0] << "\n";
    else
        cout << "impossible\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 28940 KB Output is correct
2 Correct 109 ms 38036 KB Output is correct
3 Correct 103 ms 37756 KB Output is correct
4 Correct 140 ms 38168 KB Output is correct
5 Correct 18 ms 27724 KB Output is correct
6 Correct 105 ms 38488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28984 KB Output is correct
2 Correct 107 ms 38040 KB Output is correct
3 Correct 104 ms 37744 KB Output is correct
4 Correct 134 ms 38104 KB Output is correct
5 Correct 20 ms 27744 KB Output is correct
6 Correct 101 ms 38468 KB Output is correct
7 Correct 100 ms 38212 KB Output is correct
8 Correct 105 ms 38396 KB Output is correct
9 Correct 98 ms 38316 KB Output is correct
10 Correct 122 ms 38532 KB Output is correct
11 Correct 104 ms 38404 KB Output is correct
12 Correct 101 ms 38284 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28984 KB Output is correct
2 Correct 107 ms 38040 KB Output is correct
3 Correct 104 ms 37744 KB Output is correct
4 Correct 134 ms 38104 KB Output is correct
5 Correct 20 ms 27744 KB Output is correct
6 Correct 101 ms 38468 KB Output is correct
7 Correct 100 ms 38212 KB Output is correct
8 Correct 105 ms 38396 KB Output is correct
9 Correct 98 ms 38316 KB Output is correct
10 Correct 122 ms 38532 KB Output is correct
11 Correct 104 ms 38404 KB Output is correct
12 Correct 101 ms 38284 KB Output is correct
13 Correct 97 ms 29580 KB Output is correct
14 Correct 109 ms 39088 KB Output is correct
15 Correct 105 ms 38532 KB Output is correct
16 Correct 134 ms 38768 KB Output is correct
17 Correct 18 ms 27724 KB Output is correct
18 Correct 104 ms 38464 KB Output is correct
19 Correct 102 ms 38212 KB Output is correct
20 Correct 103 ms 38276 KB Output is correct
21 Correct 98 ms 38200 KB Output is correct
22 Correct 114 ms 38532 KB Output is correct
23 Correct 113 ms 38440 KB Output is correct
24 Correct 110 ms 38436 KB Output is correct
25 Correct 1784 ms 93144 KB Output is correct
26 Correct 1689 ms 98516 KB Output is correct
27 Correct 1596 ms 94488 KB Output is correct
28 Correct 1325 ms 98260 KB Output is correct
29 Execution timed out 6055 ms 88984 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28984 KB Output is correct
2 Correct 107 ms 38040 KB Output is correct
3 Correct 104 ms 37744 KB Output is correct
4 Correct 134 ms 38104 KB Output is correct
5 Correct 20 ms 27744 KB Output is correct
6 Correct 101 ms 38468 KB Output is correct
7 Correct 100 ms 38212 KB Output is correct
8 Correct 105 ms 38396 KB Output is correct
9 Correct 98 ms 38316 KB Output is correct
10 Correct 122 ms 38532 KB Output is correct
11 Correct 104 ms 38404 KB Output is correct
12 Correct 101 ms 38284 KB Output is correct
13 Correct 97 ms 29580 KB Output is correct
14 Correct 109 ms 39088 KB Output is correct
15 Correct 105 ms 38532 KB Output is correct
16 Correct 134 ms 38768 KB Output is correct
17 Correct 18 ms 27724 KB Output is correct
18 Correct 104 ms 38464 KB Output is correct
19 Correct 102 ms 38212 KB Output is correct
20 Correct 103 ms 38276 KB Output is correct
21 Correct 98 ms 38200 KB Output is correct
22 Correct 114 ms 38532 KB Output is correct
23 Correct 113 ms 38440 KB Output is correct
24 Correct 110 ms 38436 KB Output is correct
25 Correct 1784 ms 93144 KB Output is correct
26 Correct 1689 ms 98516 KB Output is correct
27 Correct 1596 ms 94488 KB Output is correct
28 Correct 1325 ms 98260 KB Output is correct
29 Execution timed out 6055 ms 88984 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 28940 KB Output is correct
2 Correct 109 ms 38036 KB Output is correct
3 Correct 103 ms 37756 KB Output is correct
4 Correct 140 ms 38168 KB Output is correct
5 Correct 18 ms 27724 KB Output is correct
6 Correct 105 ms 38488 KB Output is correct
7 Correct 97 ms 28984 KB Output is correct
8 Correct 107 ms 38040 KB Output is correct
9 Correct 104 ms 37744 KB Output is correct
10 Correct 134 ms 38104 KB Output is correct
11 Correct 20 ms 27744 KB Output is correct
12 Correct 101 ms 38468 KB Output is correct
13 Correct 100 ms 38212 KB Output is correct
14 Correct 105 ms 38396 KB Output is correct
15 Correct 98 ms 38316 KB Output is correct
16 Correct 122 ms 38532 KB Output is correct
17 Correct 104 ms 38404 KB Output is correct
18 Correct 101 ms 38284 KB Output is correct
19 Correct 16 ms 27656 KB Output is correct
20 Correct 16 ms 27724 KB Output is correct
21 Correct 16 ms 27724 KB Output is correct
22 Correct 100 ms 29520 KB Output is correct
23 Correct 106 ms 39148 KB Output is correct
24 Correct 108 ms 38516 KB Output is correct
25 Correct 138 ms 38824 KB Output is correct
26 Correct 19 ms 27876 KB Output is correct
27 Correct 106 ms 38456 KB Output is correct
28 Correct 104 ms 38296 KB Output is correct
29 Correct 98 ms 38320 KB Output is correct
30 Correct 102 ms 38280 KB Output is correct
31 Correct 116 ms 38536 KB Output is correct
32 Correct 108 ms 38368 KB Output is correct
33 Correct 102 ms 38264 KB Output is correct
34 Incorrect 1871 ms 93984 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 28940 KB Output is correct
2 Correct 109 ms 38036 KB Output is correct
3 Correct 103 ms 37756 KB Output is correct
4 Correct 140 ms 38168 KB Output is correct
5 Correct 18 ms 27724 KB Output is correct
6 Correct 105 ms 38488 KB Output is correct
7 Correct 97 ms 28984 KB Output is correct
8 Correct 107 ms 38040 KB Output is correct
9 Correct 104 ms 37744 KB Output is correct
10 Correct 134 ms 38104 KB Output is correct
11 Correct 20 ms 27744 KB Output is correct
12 Correct 101 ms 38468 KB Output is correct
13 Correct 100 ms 38212 KB Output is correct
14 Correct 105 ms 38396 KB Output is correct
15 Correct 98 ms 38316 KB Output is correct
16 Correct 122 ms 38532 KB Output is correct
17 Correct 104 ms 38404 KB Output is correct
18 Correct 101 ms 38284 KB Output is correct
19 Correct 97 ms 29580 KB Output is correct
20 Correct 109 ms 39088 KB Output is correct
21 Correct 105 ms 38532 KB Output is correct
22 Correct 134 ms 38768 KB Output is correct
23 Correct 18 ms 27724 KB Output is correct
24 Correct 104 ms 38464 KB Output is correct
25 Correct 102 ms 38212 KB Output is correct
26 Correct 103 ms 38276 KB Output is correct
27 Correct 98 ms 38200 KB Output is correct
28 Correct 114 ms 38532 KB Output is correct
29 Correct 113 ms 38440 KB Output is correct
30 Correct 110 ms 38436 KB Output is correct
31 Correct 1784 ms 93144 KB Output is correct
32 Correct 1689 ms 98516 KB Output is correct
33 Correct 1596 ms 94488 KB Output is correct
34 Correct 1325 ms 98260 KB Output is correct
35 Execution timed out 6055 ms 88984 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 28940 KB Output is correct
2 Correct 109 ms 38036 KB Output is correct
3 Correct 103 ms 37756 KB Output is correct
4 Correct 140 ms 38168 KB Output is correct
5 Correct 18 ms 27724 KB Output is correct
6 Correct 105 ms 38488 KB Output is correct
7 Correct 97 ms 28984 KB Output is correct
8 Correct 107 ms 38040 KB Output is correct
9 Correct 104 ms 37744 KB Output is correct
10 Correct 134 ms 38104 KB Output is correct
11 Correct 20 ms 27744 KB Output is correct
12 Correct 101 ms 38468 KB Output is correct
13 Correct 100 ms 38212 KB Output is correct
14 Correct 105 ms 38396 KB Output is correct
15 Correct 98 ms 38316 KB Output is correct
16 Correct 122 ms 38532 KB Output is correct
17 Correct 104 ms 38404 KB Output is correct
18 Correct 101 ms 38284 KB Output is correct
19 Correct 97 ms 29580 KB Output is correct
20 Correct 109 ms 39088 KB Output is correct
21 Correct 105 ms 38532 KB Output is correct
22 Correct 134 ms 38768 KB Output is correct
23 Correct 18 ms 27724 KB Output is correct
24 Correct 104 ms 38464 KB Output is correct
25 Correct 102 ms 38212 KB Output is correct
26 Correct 103 ms 38276 KB Output is correct
27 Correct 98 ms 38200 KB Output is correct
28 Correct 114 ms 38532 KB Output is correct
29 Correct 113 ms 38440 KB Output is correct
30 Correct 110 ms 38436 KB Output is correct
31 Correct 1784 ms 93144 KB Output is correct
32 Correct 1689 ms 98516 KB Output is correct
33 Correct 1596 ms 94488 KB Output is correct
34 Correct 1325 ms 98260 KB Output is correct
35 Execution timed out 6055 ms 88984 KB Time limit exceeded
36 Halted 0 ms 0 KB -