oj.uz

Submission #527347

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

using namespace std;

typedef long long ll;

struct dat{
    int x, f, y;
    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];
priority_queue<dat> pq;

void update(dat tmp){
    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));
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        int x = tmp.x, f = tmp.f, y = tmp.y;
        assert(f < cycleLen[x]);

        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;
                    for(int j=0; j<cycleLen[nxt]; j++){
                        int nf = (y+1+j)%cycleLen[nxt];
                        if(nf == cycleIdx[nxt]) continue;
                        update(dat(nxt, nf, y+j+1));
                    }
                }
            }
        }
        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:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &l);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", &tmp);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23172 KB Output is correct
2 Correct 99 ms 32076 KB Output is correct
3 Correct 105 ms 31508 KB Output is correct
4 Correct 162 ms 31804 KB Output is correct
5 Correct 13 ms 21832 KB Output is correct
6 Correct 106 ms 32396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23164 KB Output is correct
2 Correct 105 ms 32264 KB Output is correct
3 Correct 92 ms 31496 KB Output is correct
4 Correct 157 ms 31796 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 113 ms 32376 KB Output is correct
7 Correct 93 ms 32224 KB Output is correct
8 Correct 87 ms 32156 KB Output is correct
9 Correct 88 ms 32148 KB Output is correct
10 Correct 145 ms 32388 KB Output is correct
11 Correct 105 ms 32196 KB Output is correct
12 Correct 96 ms 32252 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23164 KB Output is correct
2 Correct 105 ms 32264 KB Output is correct
3 Correct 92 ms 31496 KB Output is correct
4 Correct 157 ms 31796 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 113 ms 32376 KB Output is correct
7 Correct 93 ms 32224 KB Output is correct
8 Correct 87 ms 32156 KB Output is correct
9 Correct 88 ms 32148 KB Output is correct
10 Correct 145 ms 32388 KB Output is correct
11 Correct 105 ms 32196 KB Output is correct
12 Correct 96 ms 32252 KB Output is correct
13 Correct 29 ms 23616 KB Output is correct
14 Correct 104 ms 33004 KB Output is correct
15 Correct 99 ms 32412 KB Output is correct
16 Correct 179 ms 32708 KB Output is correct
17 Correct 12 ms 21828 KB Output is correct
18 Correct 97 ms 32448 KB Output is correct
19 Correct 90 ms 32216 KB Output is correct
20 Correct 90 ms 32196 KB Output is correct
21 Correct 86 ms 32248 KB Output is correct
22 Correct 145 ms 32608 KB Output is correct
23 Correct 98 ms 32204 KB Output is correct
24 Correct 93 ms 32204 KB Output is correct
25 Correct 2585 ms 117704 KB Output is correct
26 Correct 2266 ms 122012 KB Output is correct
27 Correct 2200 ms 118052 KB Output is correct
28 Correct 1603 ms 121824 KB Output is correct
29 Execution timed out 6022 ms 113160 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23164 KB Output is correct
2 Correct 105 ms 32264 KB Output is correct
3 Correct 92 ms 31496 KB Output is correct
4 Correct 157 ms 31796 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 113 ms 32376 KB Output is correct
7 Correct 93 ms 32224 KB Output is correct
8 Correct 87 ms 32156 KB Output is correct
9 Correct 88 ms 32148 KB Output is correct
10 Correct 145 ms 32388 KB Output is correct
11 Correct 105 ms 32196 KB Output is correct
12 Correct 96 ms 32252 KB Output is correct
13 Correct 29 ms 23616 KB Output is correct
14 Correct 104 ms 33004 KB Output is correct
15 Correct 99 ms 32412 KB Output is correct
16 Correct 179 ms 32708 KB Output is correct
17 Correct 12 ms 21828 KB Output is correct
18 Correct 97 ms 32448 KB Output is correct
19 Correct 90 ms 32216 KB Output is correct
20 Correct 90 ms 32196 KB Output is correct
21 Correct 86 ms 32248 KB Output is correct
22 Correct 145 ms 32608 KB Output is correct
23 Correct 98 ms 32204 KB Output is correct
24 Correct 93 ms 32204 KB Output is correct
25 Correct 2585 ms 117704 KB Output is correct
26 Correct 2266 ms 122012 KB Output is correct
27 Correct 2200 ms 118052 KB Output is correct
28 Correct 1603 ms 121824 KB Output is correct
29 Execution timed out 6022 ms 113160 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23172 KB Output is correct
2 Correct 99 ms 32076 KB Output is correct
3 Correct 105 ms 31508 KB Output is correct
4 Correct 162 ms 31804 KB Output is correct
5 Correct 13 ms 21832 KB Output is correct
6 Correct 106 ms 32396 KB Output is correct
7 Correct 26 ms 23164 KB Output is correct
8 Correct 105 ms 32264 KB Output is correct
9 Correct 92 ms 31496 KB Output is correct
10 Correct 157 ms 31796 KB Output is correct
11 Correct 13 ms 21836 KB Output is correct
12 Correct 113 ms 32376 KB Output is correct
13 Correct 93 ms 32224 KB Output is correct
14 Correct 87 ms 32156 KB Output is correct
15 Correct 88 ms 32148 KB Output is correct
16 Correct 145 ms 32388 KB Output is correct
17 Correct 105 ms 32196 KB Output is correct
18 Correct 96 ms 32252 KB Output is correct
19 Correct 12 ms 21708 KB Output is correct
20 Correct 12 ms 21836 KB Output is correct
21 Correct 13 ms 21840 KB Output is correct
22 Correct 30 ms 23628 KB Output is correct
23 Correct 121 ms 33008 KB Output is correct
24 Correct 108 ms 32388 KB Output is correct
25 Correct 206 ms 32680 KB Output is correct
26 Correct 17 ms 21852 KB Output is correct
27 Correct 121 ms 32392 KB Output is correct
28 Correct 105 ms 32136 KB Output is correct
29 Correct 97 ms 32208 KB Output is correct
30 Correct 98 ms 32104 KB Output is correct
31 Correct 170 ms 32384 KB Output is correct
32 Correct 123 ms 32468 KB Output is correct
33 Correct 97 ms 32256 KB Output is correct
34 Correct 2801 ms 118408 KB Output is correct
35 Correct 2801 ms 114508 KB Output is correct
36 Correct 2730 ms 114580 KB Output is correct
37 Incorrect 2315 ms 119896 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 23172 KB Output is correct
2 Correct 99 ms 32076 KB Output is correct
3 Correct 105 ms 31508 KB Output is correct
4 Correct 162 ms 31804 KB Output is correct
5 Correct 13 ms 21832 KB Output is correct
6 Correct 106 ms 32396 KB Output is correct
7 Correct 26 ms 23164 KB Output is correct
8 Correct 105 ms 32264 KB Output is correct
9 Correct 92 ms 31496 KB Output is correct
10 Correct 157 ms 31796 KB Output is correct
11 Correct 13 ms 21836 KB Output is correct
12 Correct 113 ms 32376 KB Output is correct
13 Correct 93 ms 32224 KB Output is correct
14 Correct 87 ms 32156 KB Output is correct
15 Correct 88 ms 32148 KB Output is correct
16 Correct 145 ms 32388 KB Output is correct
17 Correct 105 ms 32196 KB Output is correct
18 Correct 96 ms 32252 KB Output is correct
19 Correct 29 ms 23616 KB Output is correct
20 Correct 104 ms 33004 KB Output is correct
21 Correct 99 ms 32412 KB Output is correct
22 Correct 179 ms 32708 KB Output is correct
23 Correct 12 ms 21828 KB Output is correct
24 Correct 97 ms 32448 KB Output is correct
25 Correct 90 ms 32216 KB Output is correct
26 Correct 90 ms 32196 KB Output is correct
27 Correct 86 ms 32248 KB Output is correct
28 Correct 145 ms 32608 KB Output is correct
29 Correct 98 ms 32204 KB Output is correct
30 Correct 93 ms 32204 KB Output is correct
31 Correct 2585 ms 117704 KB Output is correct
32 Correct 2266 ms 122012 KB Output is correct
33 Correct 2200 ms 118052 KB Output is correct
34 Correct 1603 ms 121824 KB Output is correct
35 Execution timed out 6022 ms 113160 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23172 KB Output is correct
2 Correct 99 ms 32076 KB Output is correct
3 Correct 105 ms 31508 KB Output is correct
4 Correct 162 ms 31804 KB Output is correct
5 Correct 13 ms 21832 KB Output is correct
6 Correct 106 ms 32396 KB Output is correct
7 Correct 26 ms 23164 KB Output is correct
8 Correct 105 ms 32264 KB Output is correct
9 Correct 92 ms 31496 KB Output is correct
10 Correct 157 ms 31796 KB Output is correct
11 Correct 13 ms 21836 KB Output is correct
12 Correct 113 ms 32376 KB Output is correct
13 Correct 93 ms 32224 KB Output is correct
14 Correct 87 ms 32156 KB Output is correct
15 Correct 88 ms 32148 KB Output is correct
16 Correct 145 ms 32388 KB Output is correct
17 Correct 105 ms 32196 KB Output is correct
18 Correct 96 ms 32252 KB Output is correct
19 Correct 29 ms 23616 KB Output is correct
20 Correct 104 ms 33004 KB Output is correct
21 Correct 99 ms 32412 KB Output is correct
22 Correct 179 ms 32708 KB Output is correct
23 Correct 12 ms 21828 KB Output is correct
24 Correct 97 ms 32448 KB Output is correct
25 Correct 90 ms 32216 KB Output is correct
26 Correct 90 ms 32196 KB Output is correct
27 Correct 86 ms 32248 KB Output is correct
28 Correct 145 ms 32608 KB Output is correct
29 Correct 98 ms 32204 KB Output is correct
30 Correct 93 ms 32204 KB Output is correct
31 Correct 2585 ms 117704 KB Output is correct
32 Correct 2266 ms 122012 KB Output is correct
33 Correct 2200 ms 118052 KB Output is correct
34 Correct 1603 ms 121824 KB Output is correct
35 Execution timed out 6022 ms 113160 KB Time limit exceeded
36 Halted 0 ms 0 KB -