oj.uz

Submission #527374

# Submission time Handle Problem Language Result Execution time Memory
527374 2022-02-17T09:58:27 Z 79brue From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 241920 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--){
                        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:66:9: warning: unused variable 'pqCnt' [-Wunused-variable]
   66 |     int pqCnt = 0;
      |         ^~~~~
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 84 ms 179524 KB Output is correct
2 Correct 163 ms 188952 KB Output is correct
3 Correct 134 ms 188016 KB Output is correct
4 Correct 165 ms 188220 KB Output is correct
5 Correct 79 ms 178380 KB Output is correct
6 Correct 141 ms 188016 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 179588 KB Output is correct
2 Correct 148 ms 188888 KB Output is correct
3 Correct 174 ms 188108 KB Output is correct
4 Correct 170 ms 188232 KB Output is correct
5 Correct 68 ms 178396 KB Output is correct
6 Correct 135 ms 188020 KB Output is correct
7 Correct 154 ms 188004 KB Output is correct
8 Correct 135 ms 188076 KB Output is correct
9 Correct 140 ms 188176 KB Output is correct
10 Correct 158 ms 188152 KB Output is correct
11 Correct 140 ms 188056 KB Output is correct
12 Correct 139 ms 188008 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 179588 KB Output is correct
2 Correct 148 ms 188888 KB Output is correct
3 Correct 174 ms 188108 KB Output is correct
4 Correct 170 ms 188232 KB Output is correct
5 Correct 68 ms 178396 KB Output is correct
6 Correct 135 ms 188020 KB Output is correct
7 Correct 154 ms 188004 KB Output is correct
8 Correct 135 ms 188076 KB Output is correct
9 Correct 140 ms 188176 KB Output is correct
10 Correct 158 ms 188152 KB Output is correct
11 Correct 140 ms 188056 KB Output is correct
12 Correct 139 ms 188008 KB Output is correct
13 Correct 92 ms 179608 KB Output is correct
14 Correct 157 ms 188896 KB Output is correct
15 Correct 155 ms 188104 KB Output is correct
16 Correct 170 ms 188212 KB Output is correct
17 Correct 74 ms 178428 KB Output is correct
18 Correct 139 ms 188200 KB Output is correct
19 Correct 141 ms 188600 KB Output is correct
20 Correct 142 ms 188584 KB Output is correct
21 Correct 159 ms 188644 KB Output is correct
22 Correct 168 ms 188636 KB Output is correct
23 Correct 162 ms 188556 KB Output is correct
24 Correct 211 ms 188704 KB Output is correct
25 Correct 2031 ms 237952 KB Output is correct
26 Correct 1706 ms 241920 KB Output is correct
27 Correct 1645 ms 237848 KB Output is correct
28 Correct 1317 ms 241852 KB Output is correct
29 Execution timed out 6079 ms 233588 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 179588 KB Output is correct
2 Correct 148 ms 188888 KB Output is correct
3 Correct 174 ms 188108 KB Output is correct
4 Correct 170 ms 188232 KB Output is correct
5 Correct 68 ms 178396 KB Output is correct
6 Correct 135 ms 188020 KB Output is correct
7 Correct 154 ms 188004 KB Output is correct
8 Correct 135 ms 188076 KB Output is correct
9 Correct 140 ms 188176 KB Output is correct
10 Correct 158 ms 188152 KB Output is correct
11 Correct 140 ms 188056 KB Output is correct
12 Correct 139 ms 188008 KB Output is correct
13 Correct 92 ms 179608 KB Output is correct
14 Correct 157 ms 188896 KB Output is correct
15 Correct 155 ms 188104 KB Output is correct
16 Correct 170 ms 188212 KB Output is correct
17 Correct 74 ms 178428 KB Output is correct
18 Correct 139 ms 188200 KB Output is correct
19 Correct 141 ms 188600 KB Output is correct
20 Correct 142 ms 188584 KB Output is correct
21 Correct 159 ms 188644 KB Output is correct
22 Correct 168 ms 188636 KB Output is correct
23 Correct 162 ms 188556 KB Output is correct
24 Correct 211 ms 188704 KB Output is correct
25 Correct 2031 ms 237952 KB Output is correct
26 Correct 1706 ms 241920 KB Output is correct
27 Correct 1645 ms 237848 KB Output is correct
28 Correct 1317 ms 241852 KB Output is correct
29 Execution timed out 6079 ms 233588 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 179524 KB Output is correct
2 Correct 163 ms 188952 KB Output is correct
3 Correct 134 ms 188016 KB Output is correct
4 Correct 165 ms 188220 KB Output is correct
5 Correct 79 ms 178380 KB Output is correct
6 Correct 141 ms 188016 KB Output is correct
7 Correct 81 ms 179588 KB Output is correct
8 Correct 148 ms 188888 KB Output is correct
9 Correct 174 ms 188108 KB Output is correct
10 Correct 170 ms 188232 KB Output is correct
11 Correct 68 ms 178396 KB Output is correct
12 Correct 135 ms 188020 KB Output is correct
13 Correct 154 ms 188004 KB Output is correct
14 Correct 135 ms 188076 KB Output is correct
15 Correct 140 ms 188176 KB Output is correct
16 Correct 158 ms 188152 KB Output is correct
17 Correct 140 ms 188056 KB Output is correct
18 Correct 139 ms 188008 KB Output is correct
19 Correct 78 ms 178372 KB Output is correct
20 Correct 84 ms 178304 KB Output is correct
21 Correct 78 ms 178368 KB Output is correct
22 Correct 93 ms 179876 KB Output is correct
23 Correct 154 ms 189508 KB Output is correct
24 Correct 148 ms 188768 KB Output is correct
25 Correct 188 ms 189088 KB Output is correct
26 Correct 80 ms 178440 KB Output is correct
27 Correct 146 ms 188668 KB Output is correct
28 Correct 146 ms 188612 KB Output is correct
29 Correct 149 ms 188708 KB Output is correct
30 Correct 156 ms 188796 KB Output is correct
31 Correct 178 ms 188820 KB Output is correct
32 Correct 157 ms 188720 KB Output is correct
33 Correct 155 ms 188628 KB Output is correct
34 Correct 1780 ms 236632 KB Output is correct
35 Correct 1866 ms 233660 KB Output is correct
36 Correct 1852 ms 233428 KB Output is correct
37 Incorrect 1589 ms 238544 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 179524 KB Output is correct
2 Correct 163 ms 188952 KB Output is correct
3 Correct 134 ms 188016 KB Output is correct
4 Correct 165 ms 188220 KB Output is correct
5 Correct 79 ms 178380 KB Output is correct
6 Correct 141 ms 188016 KB Output is correct
7 Correct 81 ms 179588 KB Output is correct
8 Correct 148 ms 188888 KB Output is correct
9 Correct 174 ms 188108 KB Output is correct
10 Correct 170 ms 188232 KB Output is correct
11 Correct 68 ms 178396 KB Output is correct
12 Correct 135 ms 188020 KB Output is correct
13 Correct 154 ms 188004 KB Output is correct
14 Correct 135 ms 188076 KB Output is correct
15 Correct 140 ms 188176 KB Output is correct
16 Correct 158 ms 188152 KB Output is correct
17 Correct 140 ms 188056 KB Output is correct
18 Correct 139 ms 188008 KB Output is correct
19 Correct 92 ms 179608 KB Output is correct
20 Correct 157 ms 188896 KB Output is correct
21 Correct 155 ms 188104 KB Output is correct
22 Correct 170 ms 188212 KB Output is correct
23 Correct 74 ms 178428 KB Output is correct
24 Correct 139 ms 188200 KB Output is correct
25 Correct 141 ms 188600 KB Output is correct
26 Correct 142 ms 188584 KB Output is correct
27 Correct 159 ms 188644 KB Output is correct
28 Correct 168 ms 188636 KB Output is correct
29 Correct 162 ms 188556 KB Output is correct
30 Correct 211 ms 188704 KB Output is correct
31 Correct 2031 ms 237952 KB Output is correct
32 Correct 1706 ms 241920 KB Output is correct
33 Correct 1645 ms 237848 KB Output is correct
34 Correct 1317 ms 241852 KB Output is correct
35 Execution timed out 6079 ms 233588 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 179524 KB Output is correct
2 Correct 163 ms 188952 KB Output is correct
3 Correct 134 ms 188016 KB Output is correct
4 Correct 165 ms 188220 KB Output is correct
5 Correct 79 ms 178380 KB Output is correct
6 Correct 141 ms 188016 KB Output is correct
7 Correct 81 ms 179588 KB Output is correct
8 Correct 148 ms 188888 KB Output is correct
9 Correct 174 ms 188108 KB Output is correct
10 Correct 170 ms 188232 KB Output is correct
11 Correct 68 ms 178396 KB Output is correct
12 Correct 135 ms 188020 KB Output is correct
13 Correct 154 ms 188004 KB Output is correct
14 Correct 135 ms 188076 KB Output is correct
15 Correct 140 ms 188176 KB Output is correct
16 Correct 158 ms 188152 KB Output is correct
17 Correct 140 ms 188056 KB Output is correct
18 Correct 139 ms 188008 KB Output is correct
19 Correct 92 ms 179608 KB Output is correct
20 Correct 157 ms 188896 KB Output is correct
21 Correct 155 ms 188104 KB Output is correct
22 Correct 170 ms 188212 KB Output is correct
23 Correct 74 ms 178428 KB Output is correct
24 Correct 139 ms 188200 KB Output is correct
25 Correct 141 ms 188600 KB Output is correct
26 Correct 142 ms 188584 KB Output is correct
27 Correct 159 ms 188644 KB Output is correct
28 Correct 168 ms 188636 KB Output is correct
29 Correct 162 ms 188556 KB Output is correct
30 Correct 211 ms 188704 KB Output is correct
31 Correct 2031 ms 237952 KB Output is correct
32 Correct 1706 ms 241920 KB Output is correct
33 Correct 1645 ms 237848 KB Output is correct
34 Correct 1317 ms 241852 KB Output is correct
35 Execution timed out 6079 ms 233588 KB Time limit exceeded
36 Halted 0 ms 0 KB -