oj.uz

Submission #527692

# Submission time Handle Problem Language Result Execution time Memory
527692 2022-02-18T03:29:01 Z 79brue From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 87556 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int LIM = 1600;

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];

queue<dat> pq[LIM+5];

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[tmp.y%LIM].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));
    for(int d=0; ; d+=LIM){
        bool exist = 0;
        for(int e=0; e<LIM; e++){
            while(!pq[e].empty()){
                exist=1;
                dat tmp = pq[e].front(); pq[e].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(cycleIdx[nxt] != (y+1)%cycleLen[nxt]) update(dat(nxt, (y+1)%cycleLen[nxt], y+1));
                            int tn = (y+1-cycleIdx[nxt]-1+cycleLen[nxt]-1) / cycleLen[nxt] * cycleLen[nxt] + cycleIdx[nxt]+1;
                            update(dat(nxt, tn%cycleLen[nxt], tn));
                        }
                    }
                }
                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));
                        }
                    }
                }
            }
        }
        if(!exist) break;
    }

    printf("impossible");
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23756 KB Output is correct
2 Correct 89 ms 32904 KB Output is correct
3 Correct 87 ms 33228 KB Output is correct
4 Correct 150 ms 33420 KB Output is correct
5 Correct 12 ms 22952 KB Output is correct
6 Correct 90 ms 33136 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 99 ms 32972 KB Output is correct
3 Correct 98 ms 33240 KB Output is correct
4 Correct 147 ms 33340 KB Output is correct
5 Correct 12 ms 22860 KB Output is correct
6 Correct 98 ms 33176 KB Output is correct
7 Correct 122 ms 33184 KB Output is correct
8 Correct 88 ms 33092 KB Output is correct
9 Correct 89 ms 33112 KB Output is correct
10 Correct 124 ms 33288 KB Output is correct
11 Correct 127 ms 33220 KB Output is correct
12 Correct 97 ms 33184 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 99 ms 32972 KB Output is correct
3 Correct 98 ms 33240 KB Output is correct
4 Correct 147 ms 33340 KB Output is correct
5 Correct 12 ms 22860 KB Output is correct
6 Correct 98 ms 33176 KB Output is correct
7 Correct 122 ms 33184 KB Output is correct
8 Correct 88 ms 33092 KB Output is correct
9 Correct 89 ms 33112 KB Output is correct
10 Correct 124 ms 33288 KB Output is correct
11 Correct 127 ms 33220 KB Output is correct
12 Correct 97 ms 33184 KB Output is correct
13 Correct 30 ms 24380 KB Output is correct
14 Correct 100 ms 34036 KB Output is correct
15 Correct 98 ms 33244 KB Output is correct
16 Correct 155 ms 33252 KB Output is correct
17 Correct 12 ms 22876 KB Output is correct
18 Correct 105 ms 33192 KB Output is correct
19 Correct 113 ms 33152 KB Output is correct
20 Correct 88 ms 33204 KB Output is correct
21 Correct 89 ms 33128 KB Output is correct
22 Correct 132 ms 33272 KB Output is correct
23 Correct 107 ms 33252 KB Output is correct
24 Correct 96 ms 33088 KB Output is correct
25 Correct 2556 ms 83448 KB Output is correct
26 Correct 2329 ms 87556 KB Output is correct
27 Correct 2169 ms 83588 KB Output is correct
28 Correct 1686 ms 87544 KB Output is correct
29 Execution timed out 6060 ms 78744 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23808 KB Output is correct
2 Correct 99 ms 32972 KB Output is correct
3 Correct 98 ms 33240 KB Output is correct
4 Correct 147 ms 33340 KB Output is correct
5 Correct 12 ms 22860 KB Output is correct
6 Correct 98 ms 33176 KB Output is correct
7 Correct 122 ms 33184 KB Output is correct
8 Correct 88 ms 33092 KB Output is correct
9 Correct 89 ms 33112 KB Output is correct
10 Correct 124 ms 33288 KB Output is correct
11 Correct 127 ms 33220 KB Output is correct
12 Correct 97 ms 33184 KB Output is correct
13 Correct 30 ms 24380 KB Output is correct
14 Correct 100 ms 34036 KB Output is correct
15 Correct 98 ms 33244 KB Output is correct
16 Correct 155 ms 33252 KB Output is correct
17 Correct 12 ms 22876 KB Output is correct
18 Correct 105 ms 33192 KB Output is correct
19 Correct 113 ms 33152 KB Output is correct
20 Correct 88 ms 33204 KB Output is correct
21 Correct 89 ms 33128 KB Output is correct
22 Correct 132 ms 33272 KB Output is correct
23 Correct 107 ms 33252 KB Output is correct
24 Correct 96 ms 33088 KB Output is correct
25 Correct 2556 ms 83448 KB Output is correct
26 Correct 2329 ms 87556 KB Output is correct
27 Correct 2169 ms 83588 KB Output is correct
28 Correct 1686 ms 87544 KB Output is correct
29 Execution timed out 6060 ms 78744 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23756 KB Output is correct
2 Correct 89 ms 32904 KB Output is correct
3 Correct 87 ms 33228 KB Output is correct
4 Correct 150 ms 33420 KB Output is correct
5 Correct 12 ms 22952 KB Output is correct
6 Correct 90 ms 33136 KB Output is correct
7 Correct 28 ms 23808 KB Output is correct
8 Correct 99 ms 32972 KB Output is correct
9 Correct 98 ms 33240 KB Output is correct
10 Correct 147 ms 33340 KB Output is correct
11 Correct 12 ms 22860 KB Output is correct
12 Correct 98 ms 33176 KB Output is correct
13 Correct 122 ms 33184 KB Output is correct
14 Correct 88 ms 33092 KB Output is correct
15 Correct 89 ms 33112 KB Output is correct
16 Correct 124 ms 33288 KB Output is correct
17 Correct 127 ms 33220 KB Output is correct
18 Correct 97 ms 33184 KB Output is correct
19 Correct 12 ms 22988 KB Output is correct
20 Correct 11 ms 22860 KB Output is correct
21 Correct 16 ms 22768 KB Output is correct
22 Correct 34 ms 24372 KB Output is correct
23 Correct 112 ms 34028 KB Output is correct
24 Correct 104 ms 33228 KB Output is correct
25 Correct 173 ms 33388 KB Output is correct
26 Correct 12 ms 22880 KB Output is correct
27 Correct 96 ms 33128 KB Output is correct
28 Correct 93 ms 33244 KB Output is correct
29 Correct 94 ms 33088 KB Output is correct
30 Correct 109 ms 33220 KB Output is correct
31 Correct 143 ms 33292 KB Output is correct
32 Correct 124 ms 33248 KB Output is correct
33 Correct 96 ms 33084 KB Output is correct
34 Correct 2692 ms 82448 KB Output is correct
35 Correct 2842 ms 78860 KB Output is correct
36 Correct 2622 ms 79032 KB Output is correct
37 Incorrect 2296 ms 84288 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23756 KB Output is correct
2 Correct 89 ms 32904 KB Output is correct
3 Correct 87 ms 33228 KB Output is correct
4 Correct 150 ms 33420 KB Output is correct
5 Correct 12 ms 22952 KB Output is correct
6 Correct 90 ms 33136 KB Output is correct
7 Correct 28 ms 23808 KB Output is correct
8 Correct 99 ms 32972 KB Output is correct
9 Correct 98 ms 33240 KB Output is correct
10 Correct 147 ms 33340 KB Output is correct
11 Correct 12 ms 22860 KB Output is correct
12 Correct 98 ms 33176 KB Output is correct
13 Correct 122 ms 33184 KB Output is correct
14 Correct 88 ms 33092 KB Output is correct
15 Correct 89 ms 33112 KB Output is correct
16 Correct 124 ms 33288 KB Output is correct
17 Correct 127 ms 33220 KB Output is correct
18 Correct 97 ms 33184 KB Output is correct
19 Correct 30 ms 24380 KB Output is correct
20 Correct 100 ms 34036 KB Output is correct
21 Correct 98 ms 33244 KB Output is correct
22 Correct 155 ms 33252 KB Output is correct
23 Correct 12 ms 22876 KB Output is correct
24 Correct 105 ms 33192 KB Output is correct
25 Correct 113 ms 33152 KB Output is correct
26 Correct 88 ms 33204 KB Output is correct
27 Correct 89 ms 33128 KB Output is correct
28 Correct 132 ms 33272 KB Output is correct
29 Correct 107 ms 33252 KB Output is correct
30 Correct 96 ms 33088 KB Output is correct
31 Correct 2556 ms 83448 KB Output is correct
32 Correct 2329 ms 87556 KB Output is correct
33 Correct 2169 ms 83588 KB Output is correct
34 Correct 1686 ms 87544 KB Output is correct
35 Execution timed out 6060 ms 78744 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23756 KB Output is correct
2 Correct 89 ms 32904 KB Output is correct
3 Correct 87 ms 33228 KB Output is correct
4 Correct 150 ms 33420 KB Output is correct
5 Correct 12 ms 22952 KB Output is correct
6 Correct 90 ms 33136 KB Output is correct
7 Correct 28 ms 23808 KB Output is correct
8 Correct 99 ms 32972 KB Output is correct
9 Correct 98 ms 33240 KB Output is correct
10 Correct 147 ms 33340 KB Output is correct
11 Correct 12 ms 22860 KB Output is correct
12 Correct 98 ms 33176 KB Output is correct
13 Correct 122 ms 33184 KB Output is correct
14 Correct 88 ms 33092 KB Output is correct
15 Correct 89 ms 33112 KB Output is correct
16 Correct 124 ms 33288 KB Output is correct
17 Correct 127 ms 33220 KB Output is correct
18 Correct 97 ms 33184 KB Output is correct
19 Correct 30 ms 24380 KB Output is correct
20 Correct 100 ms 34036 KB Output is correct
21 Correct 98 ms 33244 KB Output is correct
22 Correct 155 ms 33252 KB Output is correct
23 Correct 12 ms 22876 KB Output is correct
24 Correct 105 ms 33192 KB Output is correct
25 Correct 113 ms 33152 KB Output is correct
26 Correct 88 ms 33204 KB Output is correct
27 Correct 89 ms 33128 KB Output is correct
28 Correct 132 ms 33272 KB Output is correct
29 Correct 107 ms 33252 KB Output is correct
30 Correct 96 ms 33088 KB Output is correct
31 Correct 2556 ms 83448 KB Output is correct
32 Correct 2329 ms 87556 KB Output is correct
33 Correct 2169 ms 83588 KB Output is correct
34 Correct 1686 ms 87544 KB Output is correct
35 Execution timed out 6060 ms 78744 KB Time limit exceeded
36 Halted 0 ms 0 KB -