oj.uz

Submission #527399

# Submission time Handle Problem Language Result Execution time Memory
527399 2022-02-17T11:00:24 Z 79brue From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 242208 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;
dat datList[10000000];
int datSize = 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 <= 10000000);
                        int nf = (y+1+j)%cycleLen[nxt];
                        if(nf == cycleIdx[nxt]){
                            datList[datSize++] = dat(0, 0, y+j+1);
                            datList[datSize-1].nxt = prv;
                            prv = datSize-1;
                        }
                        else{
                            datList[datSize++] = (dat(nxt, nf, y+j+1));
                            datList[datSize-1].nxt = prv;
                            prv = datSize-1;
                            visited[tmp.x][tmp.f] = 1;
                            dist[tmp.x][tmp.f] = tmp.y;
                        }
                    }
                    update(datList[datSize-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:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d", &l);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf("%d", &tmp);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 179804 KB Output is correct
2 Correct 138 ms 189560 KB Output is correct
3 Correct 134 ms 188824 KB Output is correct
4 Correct 167 ms 188740 KB Output is correct
5 Correct 67 ms 178424 KB Output is correct
6 Correct 134 ms 188692 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 179804 KB Output is correct
2 Correct 156 ms 189628 KB Output is correct
3 Correct 132 ms 188712 KB Output is correct
4 Correct 161 ms 188740 KB Output is correct
5 Correct 66 ms 178420 KB Output is correct
6 Correct 150 ms 188708 KB Output is correct
7 Correct 157 ms 188616 KB Output is correct
8 Correct 131 ms 188640 KB Output is correct
9 Correct 152 ms 188800 KB Output is correct
10 Correct 166 ms 188832 KB Output is correct
11 Correct 138 ms 188720 KB Output is correct
12 Correct 130 ms 188704 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 179804 KB Output is correct
2 Correct 156 ms 189628 KB Output is correct
3 Correct 132 ms 188712 KB Output is correct
4 Correct 161 ms 188740 KB Output is correct
5 Correct 66 ms 178420 KB Output is correct
6 Correct 150 ms 188708 KB Output is correct
7 Correct 157 ms 188616 KB Output is correct
8 Correct 131 ms 188640 KB Output is correct
9 Correct 152 ms 188800 KB Output is correct
10 Correct 166 ms 188832 KB Output is correct
11 Correct 138 ms 188720 KB Output is correct
12 Correct 130 ms 188704 KB Output is correct
13 Correct 89 ms 179780 KB Output is correct
14 Correct 149 ms 189512 KB Output is correct
15 Correct 134 ms 188776 KB Output is correct
16 Correct 181 ms 188752 KB Output is correct
17 Correct 84 ms 178400 KB Output is correct
18 Correct 131 ms 188708 KB Output is correct
19 Correct 138 ms 188612 KB Output is correct
20 Correct 154 ms 188664 KB Output is correct
21 Correct 137 ms 188740 KB Output is correct
22 Correct 186 ms 188832 KB Output is correct
23 Correct 139 ms 188688 KB Output is correct
24 Correct 141 ms 188764 KB Output is correct
25 Correct 1953 ms 237924 KB Output is correct
26 Correct 1696 ms 242208 KB Output is correct
27 Correct 1696 ms 237844 KB Output is correct
28 Correct 1351 ms 241812 KB Output is correct
29 Execution timed out 6035 ms 233592 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 179804 KB Output is correct
2 Correct 156 ms 189628 KB Output is correct
3 Correct 132 ms 188712 KB Output is correct
4 Correct 161 ms 188740 KB Output is correct
5 Correct 66 ms 178420 KB Output is correct
6 Correct 150 ms 188708 KB Output is correct
7 Correct 157 ms 188616 KB Output is correct
8 Correct 131 ms 188640 KB Output is correct
9 Correct 152 ms 188800 KB Output is correct
10 Correct 166 ms 188832 KB Output is correct
11 Correct 138 ms 188720 KB Output is correct
12 Correct 130 ms 188704 KB Output is correct
13 Correct 89 ms 179780 KB Output is correct
14 Correct 149 ms 189512 KB Output is correct
15 Correct 134 ms 188776 KB Output is correct
16 Correct 181 ms 188752 KB Output is correct
17 Correct 84 ms 178400 KB Output is correct
18 Correct 131 ms 188708 KB Output is correct
19 Correct 138 ms 188612 KB Output is correct
20 Correct 154 ms 188664 KB Output is correct
21 Correct 137 ms 188740 KB Output is correct
22 Correct 186 ms 188832 KB Output is correct
23 Correct 139 ms 188688 KB Output is correct
24 Correct 141 ms 188764 KB Output is correct
25 Correct 1953 ms 237924 KB Output is correct
26 Correct 1696 ms 242208 KB Output is correct
27 Correct 1696 ms 237844 KB Output is correct
28 Correct 1351 ms 241812 KB Output is correct
29 Execution timed out 6035 ms 233592 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 179804 KB Output is correct
2 Correct 138 ms 189560 KB Output is correct
3 Correct 134 ms 188824 KB Output is correct
4 Correct 167 ms 188740 KB Output is correct
5 Correct 67 ms 178424 KB Output is correct
6 Correct 134 ms 188692 KB Output is correct
7 Correct 83 ms 179804 KB Output is correct
8 Correct 156 ms 189628 KB Output is correct
9 Correct 132 ms 188712 KB Output is correct
10 Correct 161 ms 188740 KB Output is correct
11 Correct 66 ms 178420 KB Output is correct
12 Correct 150 ms 188708 KB Output is correct
13 Correct 157 ms 188616 KB Output is correct
14 Correct 131 ms 188640 KB Output is correct
15 Correct 152 ms 188800 KB Output is correct
16 Correct 166 ms 188832 KB Output is correct
17 Correct 138 ms 188720 KB Output is correct
18 Correct 130 ms 188704 KB Output is correct
19 Correct 65 ms 178380 KB Output is correct
20 Correct 67 ms 178320 KB Output is correct
21 Correct 66 ms 178292 KB Output is correct
22 Correct 102 ms 179876 KB Output is correct
23 Correct 158 ms 189524 KB Output is correct
24 Correct 132 ms 188664 KB Output is correct
25 Correct 164 ms 188828 KB Output is correct
26 Correct 66 ms 178384 KB Output is correct
27 Correct 131 ms 188664 KB Output is correct
28 Correct 162 ms 188692 KB Output is correct
29 Correct 134 ms 188612 KB Output is correct
30 Correct 135 ms 188620 KB Output is correct
31 Correct 188 ms 188744 KB Output is correct
32 Correct 142 ms 188724 KB Output is correct
33 Correct 146 ms 188740 KB Output is correct
34 Correct 1807 ms 236852 KB Output is correct
35 Correct 1931 ms 233752 KB Output is correct
36 Correct 1797 ms 233588 KB Output is correct
37 Incorrect 1561 ms 238764 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 179804 KB Output is correct
2 Correct 138 ms 189560 KB Output is correct
3 Correct 134 ms 188824 KB Output is correct
4 Correct 167 ms 188740 KB Output is correct
5 Correct 67 ms 178424 KB Output is correct
6 Correct 134 ms 188692 KB Output is correct
7 Correct 83 ms 179804 KB Output is correct
8 Correct 156 ms 189628 KB Output is correct
9 Correct 132 ms 188712 KB Output is correct
10 Correct 161 ms 188740 KB Output is correct
11 Correct 66 ms 178420 KB Output is correct
12 Correct 150 ms 188708 KB Output is correct
13 Correct 157 ms 188616 KB Output is correct
14 Correct 131 ms 188640 KB Output is correct
15 Correct 152 ms 188800 KB Output is correct
16 Correct 166 ms 188832 KB Output is correct
17 Correct 138 ms 188720 KB Output is correct
18 Correct 130 ms 188704 KB Output is correct
19 Correct 89 ms 179780 KB Output is correct
20 Correct 149 ms 189512 KB Output is correct
21 Correct 134 ms 188776 KB Output is correct
22 Correct 181 ms 188752 KB Output is correct
23 Correct 84 ms 178400 KB Output is correct
24 Correct 131 ms 188708 KB Output is correct
25 Correct 138 ms 188612 KB Output is correct
26 Correct 154 ms 188664 KB Output is correct
27 Correct 137 ms 188740 KB Output is correct
28 Correct 186 ms 188832 KB Output is correct
29 Correct 139 ms 188688 KB Output is correct
30 Correct 141 ms 188764 KB Output is correct
31 Correct 1953 ms 237924 KB Output is correct
32 Correct 1696 ms 242208 KB Output is correct
33 Correct 1696 ms 237844 KB Output is correct
34 Correct 1351 ms 241812 KB Output is correct
35 Execution timed out 6035 ms 233592 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 179804 KB Output is correct
2 Correct 138 ms 189560 KB Output is correct
3 Correct 134 ms 188824 KB Output is correct
4 Correct 167 ms 188740 KB Output is correct
5 Correct 67 ms 178424 KB Output is correct
6 Correct 134 ms 188692 KB Output is correct
7 Correct 83 ms 179804 KB Output is correct
8 Correct 156 ms 189628 KB Output is correct
9 Correct 132 ms 188712 KB Output is correct
10 Correct 161 ms 188740 KB Output is correct
11 Correct 66 ms 178420 KB Output is correct
12 Correct 150 ms 188708 KB Output is correct
13 Correct 157 ms 188616 KB Output is correct
14 Correct 131 ms 188640 KB Output is correct
15 Correct 152 ms 188800 KB Output is correct
16 Correct 166 ms 188832 KB Output is correct
17 Correct 138 ms 188720 KB Output is correct
18 Correct 130 ms 188704 KB Output is correct
19 Correct 89 ms 179780 KB Output is correct
20 Correct 149 ms 189512 KB Output is correct
21 Correct 134 ms 188776 KB Output is correct
22 Correct 181 ms 188752 KB Output is correct
23 Correct 84 ms 178400 KB Output is correct
24 Correct 131 ms 188708 KB Output is correct
25 Correct 138 ms 188612 KB Output is correct
26 Correct 154 ms 188664 KB Output is correct
27 Correct 137 ms 188740 KB Output is correct
28 Correct 186 ms 188832 KB Output is correct
29 Correct 139 ms 188688 KB Output is correct
30 Correct 141 ms 188764 KB Output is correct
31 Correct 1953 ms 237924 KB Output is correct
32 Correct 1696 ms 242208 KB Output is correct
33 Correct 1696 ms 237844 KB Output is correct
34 Correct 1351 ms 241812 KB Output is correct
35 Execution timed out 6035 ms 233592 KB Time limit exceeded
36 Halted 0 ms 0 KB -