oj.uz

Submission #426378

# Submission time Handle Problem Language Result Execution time Memory
426378 2021-06-13T21:31:46 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
25 / 100
 6000 ms 136300 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
int readInt() {
    char c;
    int n = 0;
    while ((c=getchar()) < '0');
    n = c-'0';
    while ((c=getchar()) >= '0') n = n*10+c-'0';
    return n;
}

vi adjList[250000];
int pos[250000];
pair<int,pii> p[250000];
bool comp(int a,int b) {
    return p[a] < p[b];
}
vi dist[250000];
int done[250000],done2[250000];
vi Q[1000000];
int main() {
    int i,j;
    int N,M,K;
    int u,v,l;
    scanf("%d %d",&N,&M);
    for (i = 0; i < M; i++) {
        u = readInt();
        v = readInt();
        u--,v--;
        adjList[u].pb(v);
        adjList[v].pb(u);
    }
    scanf("%d",&K);
    for (i = 0; i < K; i++) {
        scanf("%d",&l);
        for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
    }

    for (i = 0; i < N; i++) {
        if (p[i].first == 0) p[i].first = 1;
        dist[i].resize(p[i].first);
        fill(dist[i].begin(),dist[i].end(),-1);
        sort(adjList[i].begin(),adjList[i].end(),comp);
        while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first <= 1)) pos[i]++;
    }
    int pp = 0;
    dist[0][0] = 0,Q[0].pb(0);
    while (1) {
        while ((pp < 1000000) && (Q[pp].empty())) pp++;
        if (pp == 1000000) break;
        int u = Q[pp].back();
        int d = pp;
        Q[pp].pop_back();

        if (d > dist[u][d % p[u].first]) continue;
        else if (u == N-1) {
            printf("%d\n",d);
            return 0;
        }
        i = 0;
        if (done2[u]) i = pos[u];
        for (; i < adjList[u].size(); i++) {
            int v = adjList[u][i],t = d;
            for (j = 0; j < ((p[u].first == 1) ? p[v].first:1); j++) {
                if (done[v] && (p[u].first == 1)) break;
                int bad = 0;
                if (p[v].first != 1) {
                    if (((d+1) % p[v].first) == p[v].second.first) bad = 1;
                    if (((d % p[v].first) == p[v].second.first) && (p[u].second.second == p[v].second.second) \
                        && (p[u].second.first == ((p[v].second.first+1) % p[v].first))) bad = 1;
                }
                if (!bad) {
                    if ((dist[v][(d+1) % p[v].first] == -1) || (d+1 < dist[v][(d+1) % p[v].first])) {
                        dist[v][(d+1) % p[v].first] = d+1;
                        Q[d+1].pb(v);
                    }
                }
                d++;
                if ((p[u].first != 1) && ((d % p[u].first) == p[u].second.first)) break;
            }
            if ((p[u].first == 1) && (p[v].first != 1)) done[v] = 1;
            d = t+p[u].first;
            int bad = 0;
            if (p[v].first != 1) {
                if (((d+1) % p[v].first) == p[v].second.first) bad = 1;
                if (((d % p[v].first) == p[v].second.first) && (p[u].second.second == p[v].second.second) \
                    && (p[u].second.first == ((p[v].second.first+1) % p[v].first))) bad = 1;
            }
            if (!bad) {
                if ((dist[v][(d+1) % p[v].first] == -1) || (d+1 < dist[v][(d+1) % p[v].first])) {
                    dist[v][(d+1) % p[v].first] = d+1;
                    Q[d+1].pb(v);
                }
            }
            d = t;
        }
        done2[u] = 1;
    }
    printf("impossible\n");

    return 0;
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first <= 1)) pos[i]++;
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (; i < adjList[u].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d",&l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:42:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
      |                                 ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37064 KB Output is correct
2 Correct 125 ms 48068 KB Output is correct
3 Correct 145 ms 46680 KB Output is correct
4 Correct 161 ms 46264 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 105 ms 46484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37044 KB Output is correct
2 Correct 125 ms 48148 KB Output is correct
3 Correct 104 ms 46620 KB Output is correct
4 Correct 170 ms 46252 KB Output is correct
5 Correct 24 ms 35528 KB Output is correct
6 Correct 115 ms 46440 KB Output is correct
7 Correct 112 ms 46660 KB Output is correct
8 Correct 116 ms 46916 KB Output is correct
9 Correct 111 ms 46864 KB Output is correct
10 Correct 144 ms 45508 KB Output is correct
11 Correct 106 ms 45052 KB Output is correct
12 Correct 102 ms 46356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37044 KB Output is correct
2 Correct 125 ms 48148 KB Output is correct
3 Correct 104 ms 46620 KB Output is correct
4 Correct 170 ms 46252 KB Output is correct
5 Correct 24 ms 35528 KB Output is correct
6 Correct 115 ms 46440 KB Output is correct
7 Correct 112 ms 46660 KB Output is correct
8 Correct 116 ms 46916 KB Output is correct
9 Correct 111 ms 46864 KB Output is correct
10 Correct 144 ms 45508 KB Output is correct
11 Correct 106 ms 45052 KB Output is correct
12 Correct 102 ms 46356 KB Output is correct
13 Correct 42 ms 37056 KB Output is correct
14 Correct 179 ms 48088 KB Output is correct
15 Correct 124 ms 46916 KB Output is correct
16 Correct 170 ms 46136 KB Output is correct
17 Correct 26 ms 35532 KB Output is correct
18 Correct 109 ms 46416 KB Output is correct
19 Correct 105 ms 46560 KB Output is correct
20 Correct 115 ms 46908 KB Output is correct
21 Correct 142 ms 46892 KB Output is correct
22 Correct 134 ms 45468 KB Output is correct
23 Correct 114 ms 44956 KB Output is correct
24 Correct 127 ms 46432 KB Output is correct
25 Correct 2581 ms 112356 KB Output is correct
26 Correct 2517 ms 117196 KB Output is correct
27 Correct 2153 ms 113988 KB Output is correct
28 Correct 1591 ms 118136 KB Output is correct
29 Correct 2396 ms 105844 KB Output is correct
30 Correct 2394 ms 89468 KB Output is correct
31 Correct 2600 ms 98340 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37044 KB Output is correct
2 Correct 125 ms 48148 KB Output is correct
3 Correct 104 ms 46620 KB Output is correct
4 Correct 170 ms 46252 KB Output is correct
5 Correct 24 ms 35528 KB Output is correct
6 Correct 115 ms 46440 KB Output is correct
7 Correct 112 ms 46660 KB Output is correct
8 Correct 116 ms 46916 KB Output is correct
9 Correct 111 ms 46864 KB Output is correct
10 Correct 144 ms 45508 KB Output is correct
11 Correct 106 ms 45052 KB Output is correct
12 Correct 102 ms 46356 KB Output is correct
13 Correct 42 ms 37056 KB Output is correct
14 Correct 179 ms 48088 KB Output is correct
15 Correct 124 ms 46916 KB Output is correct
16 Correct 170 ms 46136 KB Output is correct
17 Correct 26 ms 35532 KB Output is correct
18 Correct 109 ms 46416 KB Output is correct
19 Correct 105 ms 46560 KB Output is correct
20 Correct 115 ms 46908 KB Output is correct
21 Correct 142 ms 46892 KB Output is correct
22 Correct 134 ms 45468 KB Output is correct
23 Correct 114 ms 44956 KB Output is correct
24 Correct 127 ms 46432 KB Output is correct
25 Correct 2581 ms 112356 KB Output is correct
26 Correct 2517 ms 117196 KB Output is correct
27 Correct 2153 ms 113988 KB Output is correct
28 Correct 1591 ms 118136 KB Output is correct
29 Correct 2396 ms 105844 KB Output is correct
30 Correct 2394 ms 89468 KB Output is correct
31 Correct 2600 ms 98340 KB Output is correct
32 Correct 42 ms 37048 KB Output is correct
33 Correct 136 ms 48132 KB Output is correct
34 Correct 165 ms 46656 KB Output is correct
35 Correct 161 ms 46148 KB Output is correct
36 Correct 27 ms 35528 KB Output is correct
37 Correct 116 ms 46388 KB Output is correct
38 Correct 138 ms 46708 KB Output is correct
39 Correct 139 ms 46828 KB Output is correct
40 Correct 104 ms 46868 KB Output is correct
41 Correct 117 ms 45540 KB Output is correct
42 Correct 113 ms 44944 KB Output is correct
43 Correct 145 ms 46424 KB Output is correct
44 Correct 2419 ms 94856 KB Output is correct
45 Correct 2337 ms 99776 KB Output is correct
46 Correct 2242 ms 96564 KB Output is correct
47 Correct 1601 ms 100736 KB Output is correct
48 Correct 2227 ms 88272 KB Output is correct
49 Correct 2336 ms 89712 KB Output is correct
50 Correct 2601 ms 98508 KB Output is correct
51 Correct 3074 ms 115648 KB Output is correct
52 Correct 3049 ms 136300 KB Output is correct
53 Correct 2599 ms 117976 KB Output is correct
54 Correct 1614 ms 94032 KB Output is correct
55 Execution timed out 6039 ms 111260 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37064 KB Output is correct
2 Correct 125 ms 48068 KB Output is correct
3 Correct 145 ms 46680 KB Output is correct
4 Correct 161 ms 46264 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 105 ms 46484 KB Output is correct
7 Correct 39 ms 37044 KB Output is correct
8 Correct 125 ms 48148 KB Output is correct
9 Correct 104 ms 46620 KB Output is correct
10 Correct 170 ms 46252 KB Output is correct
11 Correct 24 ms 35528 KB Output is correct
12 Correct 115 ms 46440 KB Output is correct
13 Correct 112 ms 46660 KB Output is correct
14 Correct 116 ms 46916 KB Output is correct
15 Correct 111 ms 46864 KB Output is correct
16 Correct 144 ms 45508 KB Output is correct
17 Correct 106 ms 45052 KB Output is correct
18 Correct 102 ms 46356 KB Output is correct
19 Correct 23 ms 35456 KB Output is correct
20 Correct 22 ms 35396 KB Output is correct
21 Correct 27 ms 35508 KB Output is correct
22 Correct 43 ms 37060 KB Output is correct
23 Correct 140 ms 48084 KB Output is correct
24 Correct 112 ms 46652 KB Output is correct
25 Correct 162 ms 46236 KB Output is correct
26 Correct 23 ms 35532 KB Output is correct
27 Correct 146 ms 46440 KB Output is correct
28 Correct 112 ms 46568 KB Output is correct
29 Correct 120 ms 46872 KB Output is correct
30 Correct 119 ms 46960 KB Output is correct
31 Correct 133 ms 45484 KB Output is correct
32 Correct 120 ms 45108 KB Output is correct
33 Correct 118 ms 46424 KB Output is correct
34 Correct 2539 ms 110068 KB Output is correct
35 Correct 2581 ms 105276 KB Output is correct
36 Correct 2870 ms 107400 KB Output is correct
37 Correct 2363 ms 112764 KB Output is correct
38 Correct 2516 ms 132088 KB Output is correct
39 Correct 2320 ms 126248 KB Output is correct
40 Correct 2200 ms 126292 KB Output is correct
41 Correct 2358 ms 126104 KB Output is correct
42 Correct 2508 ms 131992 KB Output is correct
43 Correct 2581 ms 131928 KB Output is correct
44 Correct 2595 ms 134936 KB Output is correct
45 Incorrect 1845 ms 124148 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37064 KB Output is correct
2 Correct 125 ms 48068 KB Output is correct
3 Correct 145 ms 46680 KB Output is correct
4 Correct 161 ms 46264 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 105 ms 46484 KB Output is correct
7 Correct 39 ms 37044 KB Output is correct
8 Correct 125 ms 48148 KB Output is correct
9 Correct 104 ms 46620 KB Output is correct
10 Correct 170 ms 46252 KB Output is correct
11 Correct 24 ms 35528 KB Output is correct
12 Correct 115 ms 46440 KB Output is correct
13 Correct 112 ms 46660 KB Output is correct
14 Correct 116 ms 46916 KB Output is correct
15 Correct 111 ms 46864 KB Output is correct
16 Correct 144 ms 45508 KB Output is correct
17 Correct 106 ms 45052 KB Output is correct
18 Correct 102 ms 46356 KB Output is correct
19 Correct 42 ms 37056 KB Output is correct
20 Correct 179 ms 48088 KB Output is correct
21 Correct 124 ms 46916 KB Output is correct
22 Correct 170 ms 46136 KB Output is correct
23 Correct 26 ms 35532 KB Output is correct
24 Correct 109 ms 46416 KB Output is correct
25 Correct 105 ms 46560 KB Output is correct
26 Correct 115 ms 46908 KB Output is correct
27 Correct 142 ms 46892 KB Output is correct
28 Correct 134 ms 45468 KB Output is correct
29 Correct 114 ms 44956 KB Output is correct
30 Correct 127 ms 46432 KB Output is correct
31 Correct 2581 ms 112356 KB Output is correct
32 Correct 2517 ms 117196 KB Output is correct
33 Correct 2153 ms 113988 KB Output is correct
34 Correct 1591 ms 118136 KB Output is correct
35 Correct 2396 ms 105844 KB Output is correct
36 Correct 2394 ms 89468 KB Output is correct
37 Correct 2600 ms 98340 KB Output is correct
38 Correct 23 ms 35456 KB Output is correct
39 Correct 22 ms 35396 KB Output is correct
40 Correct 27 ms 35508 KB Output is correct
41 Correct 43 ms 37060 KB Output is correct
42 Correct 140 ms 48084 KB Output is correct
43 Correct 112 ms 46652 KB Output is correct
44 Correct 162 ms 46236 KB Output is correct
45 Correct 23 ms 35532 KB Output is correct
46 Correct 146 ms 46440 KB Output is correct
47 Correct 112 ms 46568 KB Output is correct
48 Correct 120 ms 46872 KB Output is correct
49 Correct 119 ms 46960 KB Output is correct
50 Correct 133 ms 45484 KB Output is correct
51 Correct 120 ms 45108 KB Output is correct
52 Correct 118 ms 46424 KB Output is correct
53 Correct 2539 ms 110068 KB Output is correct
54 Correct 2581 ms 105276 KB Output is correct
55 Correct 2870 ms 107400 KB Output is correct
56 Correct 2363 ms 112764 KB Output is correct
57 Correct 2516 ms 132088 KB Output is correct
58 Correct 2320 ms 126248 KB Output is correct
59 Correct 2200 ms 126292 KB Output is correct
60 Correct 2358 ms 126104 KB Output is correct
61 Correct 2508 ms 131992 KB Output is correct
62 Correct 2581 ms 131928 KB Output is correct
63 Correct 2595 ms 134936 KB Output is correct
64 Incorrect 1845 ms 124148 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37064 KB Output is correct
2 Correct 125 ms 48068 KB Output is correct
3 Correct 145 ms 46680 KB Output is correct
4 Correct 161 ms 46264 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 105 ms 46484 KB Output is correct
7 Correct 39 ms 37044 KB Output is correct
8 Correct 125 ms 48148 KB Output is correct
9 Correct 104 ms 46620 KB Output is correct
10 Correct 170 ms 46252 KB Output is correct
11 Correct 24 ms 35528 KB Output is correct
12 Correct 115 ms 46440 KB Output is correct
13 Correct 112 ms 46660 KB Output is correct
14 Correct 116 ms 46916 KB Output is correct
15 Correct 111 ms 46864 KB Output is correct
16 Correct 144 ms 45508 KB Output is correct
17 Correct 106 ms 45052 KB Output is correct
18 Correct 102 ms 46356 KB Output is correct
19 Correct 42 ms 37056 KB Output is correct
20 Correct 179 ms 48088 KB Output is correct
21 Correct 124 ms 46916 KB Output is correct
22 Correct 170 ms 46136 KB Output is correct
23 Correct 26 ms 35532 KB Output is correct
24 Correct 109 ms 46416 KB Output is correct
25 Correct 105 ms 46560 KB Output is correct
26 Correct 115 ms 46908 KB Output is correct
27 Correct 142 ms 46892 KB Output is correct
28 Correct 134 ms 45468 KB Output is correct
29 Correct 114 ms 44956 KB Output is correct
30 Correct 127 ms 46432 KB Output is correct
31 Correct 2581 ms 112356 KB Output is correct
32 Correct 2517 ms 117196 KB Output is correct
33 Correct 2153 ms 113988 KB Output is correct
34 Correct 1591 ms 118136 KB Output is correct
35 Correct 2396 ms 105844 KB Output is correct
36 Correct 2394 ms 89468 KB Output is correct
37 Correct 2600 ms 98340 KB Output is correct
38 Correct 42 ms 37048 KB Output is correct
39 Correct 136 ms 48132 KB Output is correct
40 Correct 165 ms 46656 KB Output is correct
41 Correct 161 ms 46148 KB Output is correct
42 Correct 27 ms 35528 KB Output is correct
43 Correct 116 ms 46388 KB Output is correct
44 Correct 138 ms 46708 KB Output is correct
45 Correct 139 ms 46828 KB Output is correct
46 Correct 104 ms 46868 KB Output is correct
47 Correct 117 ms 45540 KB Output is correct
48 Correct 113 ms 44944 KB Output is correct
49 Correct 145 ms 46424 KB Output is correct
50 Correct 2419 ms 94856 KB Output is correct
51 Correct 2337 ms 99776 KB Output is correct
52 Correct 2242 ms 96564 KB Output is correct
53 Correct 1601 ms 100736 KB Output is correct
54 Correct 2227 ms 88272 KB Output is correct
55 Correct 2336 ms 89712 KB Output is correct
56 Correct 2601 ms 98508 KB Output is correct
57 Correct 3074 ms 115648 KB Output is correct
58 Correct 3049 ms 136300 KB Output is correct
59 Correct 2599 ms 117976 KB Output is correct
60 Correct 1614 ms 94032 KB Output is correct
61 Execution timed out 6039 ms 111260 KB Time limit exceeded
62 Halted 0 ms 0 KB -