oj.uz

Submission #527368

# Submission time Handle Problem Language Result Execution time Memory
527368 2022-02-17T09:55:33 Z 79brue From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 2005 ms 183844 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, f, y;
    int nxt=0;
    dat(){}
    dat(int x, int f, int y): x(x), f(f), y(y){}

    bool operator<(const dat &r)const{
        return y>r.y;
    }
};

int n, m, k;
vector<int> link[250002];
int cycleLen[250002];
int cycleIdx[250002];
vector<int> dist[250002];
vector<bool> visited[250002];
queue<dat> pq;
vector<dat> datList (3);

void update(dat tmp){
    if(tmp.x){
        if(visited[tmp.x][tmp.f]) return;
        visited[tmp.x][tmp.f] = 1;
        dist[tmp.x][tmp.f] = tmp.y;
    }
    pq.push(tmp);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    scanf("%d", &k);
    while(k--){
        int l;
        scanf("%d", &l);
        for(int j=0; j<l; j++){
            int tmp;
            scanf("%d", &tmp);
            cycleLen[tmp] = l;
            cycleIdx[tmp] = j;
        }
    }

    for(int i=1; i<=n; i++){
        if(!cycleLen[i]) cycleLen[i] = 1;
        dist[i] = vector<int> (cycleLen[i], 1e9);
        visited[i].resize(cycleLen[i]);
    }

    update(dat(1, 0, 0));

    int pqCnt = 0;
    while(!pq.empty()){
        dat tmp = pq.front(); pq.pop();
        int x = tmp.x, f = tmp.f, y = tmp.y;
//        printf("%d %d: %d\n", x, f, y);
//        assert(f < cycleLen[x]);

        if(tmp.nxt){
            pq.push(datList[tmp.nxt]);
        }
        if(tmp.x == 0) continue;

        if(x==n){
            printf("%d", y);
            return 0;
        }

        if(cycleLen[x] == 1){
            for(int nxt: link[x]){
                if(cycleLen[nxt] == 1) update(dat(nxt, 0, y+1));
                else{
                    if(visited[nxt][0] || visited[nxt][1] || visited[nxt][2]) continue;
                    int prv = 0;
                    for(int j=cycleLen[nxt]-1; j>=0; j--){
        assert(++pqCnt <= 1000000);
                        int nf = (y+1+j)%cycleLen[nxt];
                        if(nf == cycleIdx[nxt]){
                            datList.push_back(dat(0, 0, y+j+1));
                            datList.back().nxt = prv;
                            prv = (int)datList.size() - 1;
                        }
                        else{
                            datList.push_back(dat(nxt, nf, y+j+1));
                            datList.back().nxt = prv;
                            prv = (int)datList.size() - 1;
                            visited[tmp.x][tmp.f] = 1;
                            dist[tmp.x][tmp.f] = tmp.y;
                        }
                    }
                    update(datList.back());
                }
            }
        }
        else{
            for(int nxt: link[x]){
                if(cycleLen[nxt] == 1) update(dat(nxt, 0, y+1));
                else{
                    int nf = (f+1)%cycleLen[nxt];
                    if(nf == cycleIdx[nxt]) continue;
                    if(nf == cycleIdx[x] && f%cycleLen[nxt] == cycleIdx[nxt]) continue;
                    update(dat(nxt, nf, y+1));
                }
            }
        }
    }

    printf("impossible");
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d", &l);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d", &tmp);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23180 KB Output is correct
2 Correct 87 ms 31888 KB Output is correct
3 Correct 90 ms 31400 KB Output is correct
4 Correct 134 ms 37332 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 95 ms 31360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23260 KB Output is correct
2 Correct 87 ms 31792 KB Output is correct
3 Correct 87 ms 31500 KB Output is correct
4 Correct 111 ms 37344 KB Output is correct
5 Correct 11 ms 21788 KB Output is correct
6 Correct 78 ms 31480 KB Output is correct
7 Correct 78 ms 30916 KB Output is correct
8 Correct 89 ms 31200 KB Output is correct
9 Correct 104 ms 31036 KB Output is correct
10 Correct 115 ms 43440 KB Output is correct
11 Correct 101 ms 34152 KB Output is correct
12 Correct 78 ms 31172 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23260 KB Output is correct
2 Correct 87 ms 31792 KB Output is correct
3 Correct 87 ms 31500 KB Output is correct
4 Correct 111 ms 37344 KB Output is correct
5 Correct 11 ms 21788 KB Output is correct
6 Correct 78 ms 31480 KB Output is correct
7 Correct 78 ms 30916 KB Output is correct
8 Correct 89 ms 31200 KB Output is correct
9 Correct 104 ms 31036 KB Output is correct
10 Correct 115 ms 43440 KB Output is correct
11 Correct 101 ms 34152 KB Output is correct
12 Correct 78 ms 31172 KB Output is correct
13 Correct 27 ms 23164 KB Output is correct
14 Correct 103 ms 31904 KB Output is correct
15 Correct 88 ms 31496 KB Output is correct
16 Correct 111 ms 37360 KB Output is correct
17 Correct 11 ms 21860 KB Output is correct
18 Correct 79 ms 31364 KB Output is correct
19 Correct 80 ms 30952 KB Output is correct
20 Correct 87 ms 31036 KB Output is correct
21 Correct 81 ms 31008 KB Output is correct
22 Correct 111 ms 43452 KB Output is correct
23 Correct 90 ms 34160 KB Output is correct
24 Correct 78 ms 31220 KB Output is correct
25 Correct 1703 ms 79208 KB Output is correct
26 Correct 1596 ms 83252 KB Output is correct
27 Correct 1480 ms 79692 KB Output is correct
28 Correct 1209 ms 83216 KB Output is correct
29 Runtime error 1450 ms 183844 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23260 KB Output is correct
2 Correct 87 ms 31792 KB Output is correct
3 Correct 87 ms 31500 KB Output is correct
4 Correct 111 ms 37344 KB Output is correct
5 Correct 11 ms 21788 KB Output is correct
6 Correct 78 ms 31480 KB Output is correct
7 Correct 78 ms 30916 KB Output is correct
8 Correct 89 ms 31200 KB Output is correct
9 Correct 104 ms 31036 KB Output is correct
10 Correct 115 ms 43440 KB Output is correct
11 Correct 101 ms 34152 KB Output is correct
12 Correct 78 ms 31172 KB Output is correct
13 Correct 27 ms 23164 KB Output is correct
14 Correct 103 ms 31904 KB Output is correct
15 Correct 88 ms 31496 KB Output is correct
16 Correct 111 ms 37360 KB Output is correct
17 Correct 11 ms 21860 KB Output is correct
18 Correct 79 ms 31364 KB Output is correct
19 Correct 80 ms 30952 KB Output is correct
20 Correct 87 ms 31036 KB Output is correct
21 Correct 81 ms 31008 KB Output is correct
22 Correct 111 ms 43452 KB Output is correct
23 Correct 90 ms 34160 KB Output is correct
24 Correct 78 ms 31220 KB Output is correct
25 Correct 1703 ms 79208 KB Output is correct
26 Correct 1596 ms 83252 KB Output is correct
27 Correct 1480 ms 79692 KB Output is correct
28 Correct 1209 ms 83216 KB Output is correct
29 Runtime error 1450 ms 183844 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23180 KB Output is correct
2 Correct 87 ms 31888 KB Output is correct
3 Correct 90 ms 31400 KB Output is correct
4 Correct 134 ms 37332 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 95 ms 31360 KB Output is correct
7 Correct 26 ms 23260 KB Output is correct
8 Correct 87 ms 31792 KB Output is correct
9 Correct 87 ms 31500 KB Output is correct
10 Correct 111 ms 37344 KB Output is correct
11 Correct 11 ms 21788 KB Output is correct
12 Correct 78 ms 31480 KB Output is correct
13 Correct 78 ms 30916 KB Output is correct
14 Correct 89 ms 31200 KB Output is correct
15 Correct 104 ms 31036 KB Output is correct
16 Correct 115 ms 43440 KB Output is correct
17 Correct 101 ms 34152 KB Output is correct
18 Correct 78 ms 31172 KB Output is correct
19 Correct 12 ms 21836 KB Output is correct
20 Correct 11 ms 21708 KB Output is correct
21 Correct 11 ms 21836 KB Output is correct
22 Correct 30 ms 23260 KB Output is correct
23 Correct 96 ms 31908 KB Output is correct
24 Correct 103 ms 31384 KB Output is correct
25 Correct 115 ms 37332 KB Output is correct
26 Correct 13 ms 21836 KB Output is correct
27 Correct 89 ms 31376 KB Output is correct
28 Correct 83 ms 30944 KB Output is correct
29 Correct 84 ms 31044 KB Output is correct
30 Correct 84 ms 30956 KB Output is correct
31 Correct 107 ms 43456 KB Output is correct
32 Correct 101 ms 34244 KB Output is correct
33 Correct 85 ms 31172 KB Output is correct
34 Correct 2005 ms 79448 KB Output is correct
35 Correct 1891 ms 76336 KB Output is correct
36 Correct 1795 ms 76284 KB Output is correct
37 Incorrect 1660 ms 81532 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23180 KB Output is correct
2 Correct 87 ms 31888 KB Output is correct
3 Correct 90 ms 31400 KB Output is correct
4 Correct 134 ms 37332 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 95 ms 31360 KB Output is correct
7 Correct 26 ms 23260 KB Output is correct
8 Correct 87 ms 31792 KB Output is correct
9 Correct 87 ms 31500 KB Output is correct
10 Correct 111 ms 37344 KB Output is correct
11 Correct 11 ms 21788 KB Output is correct
12 Correct 78 ms 31480 KB Output is correct
13 Correct 78 ms 30916 KB Output is correct
14 Correct 89 ms 31200 KB Output is correct
15 Correct 104 ms 31036 KB Output is correct
16 Correct 115 ms 43440 KB Output is correct
17 Correct 101 ms 34152 KB Output is correct
18 Correct 78 ms 31172 KB Output is correct
19 Correct 27 ms 23164 KB Output is correct
20 Correct 103 ms 31904 KB Output is correct
21 Correct 88 ms 31496 KB Output is correct
22 Correct 111 ms 37360 KB Output is correct
23 Correct 11 ms 21860 KB Output is correct
24 Correct 79 ms 31364 KB Output is correct
25 Correct 80 ms 30952 KB Output is correct
26 Correct 87 ms 31036 KB Output is correct
27 Correct 81 ms 31008 KB Output is correct
28 Correct 111 ms 43452 KB Output is correct
29 Correct 90 ms 34160 KB Output is correct
30 Correct 78 ms 31220 KB Output is correct
31 Correct 1703 ms 79208 KB Output is correct
32 Correct 1596 ms 83252 KB Output is correct
33 Correct 1480 ms 79692 KB Output is correct
34 Correct 1209 ms 83216 KB Output is correct
35 Runtime error 1450 ms 183844 KB Execution killed with signal 6
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23180 KB Output is correct
2 Correct 87 ms 31888 KB Output is correct
3 Correct 90 ms 31400 KB Output is correct
4 Correct 134 ms 37332 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 95 ms 31360 KB Output is correct
7 Correct 26 ms 23260 KB Output is correct
8 Correct 87 ms 31792 KB Output is correct
9 Correct 87 ms 31500 KB Output is correct
10 Correct 111 ms 37344 KB Output is correct
11 Correct 11 ms 21788 KB Output is correct
12 Correct 78 ms 31480 KB Output is correct
13 Correct 78 ms 30916 KB Output is correct
14 Correct 89 ms 31200 KB Output is correct
15 Correct 104 ms 31036 KB Output is correct
16 Correct 115 ms 43440 KB Output is correct
17 Correct 101 ms 34152 KB Output is correct
18 Correct 78 ms 31172 KB Output is correct
19 Correct 27 ms 23164 KB Output is correct
20 Correct 103 ms 31904 KB Output is correct
21 Correct 88 ms 31496 KB Output is correct
22 Correct 111 ms 37360 KB Output is correct
23 Correct 11 ms 21860 KB Output is correct
24 Correct 79 ms 31364 KB Output is correct
25 Correct 80 ms 30952 KB Output is correct
26 Correct 87 ms 31036 KB Output is correct
27 Correct 81 ms 31008 KB Output is correct
28 Correct 111 ms 43452 KB Output is correct
29 Correct 90 ms 34160 KB Output is correct
30 Correct 78 ms 31220 KB Output is correct
31 Correct 1703 ms 79208 KB Output is correct
32 Correct 1596 ms 83252 KB Output is correct
33 Correct 1480 ms 79692 KB Output is correct
34 Correct 1209 ms 83216 KB Output is correct
35 Runtime error 1450 ms 183844 KB Execution killed with signal 6
36 Halted 0 ms 0 KB -