oj.uz

Submission #426379

# Submission time Handle Problem Language Result Execution time Memory
426379 2021-06-13T21:36:26 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
25 / 100
 6000 ms 136244 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 += p[u].first;
                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 -= p[u].first;
                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 39 ms 37072 KB Output is correct
2 Correct 112 ms 48132 KB Output is correct
3 Correct 127 ms 46656 KB Output is correct
4 Correct 181 ms 46264 KB Output is correct
5 Correct 21 ms 35648 KB Output is correct
6 Correct 101 ms 46396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37096 KB Output is correct
2 Correct 127 ms 48164 KB Output is correct
3 Correct 125 ms 46680 KB Output is correct
4 Correct 206 ms 46148 KB Output is correct
5 Correct 22 ms 35596 KB Output is correct
6 Correct 121 ms 46372 KB Output is correct
7 Correct 123 ms 46536 KB Output is correct
8 Correct 159 ms 46928 KB Output is correct
9 Correct 114 ms 46912 KB Output is correct
10 Correct 123 ms 45528 KB Output is correct
11 Correct 125 ms 45092 KB Output is correct
12 Correct 117 ms 46400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37096 KB Output is correct
2 Correct 127 ms 48164 KB Output is correct
3 Correct 125 ms 46680 KB Output is correct
4 Correct 206 ms 46148 KB Output is correct
5 Correct 22 ms 35596 KB Output is correct
6 Correct 121 ms 46372 KB Output is correct
7 Correct 123 ms 46536 KB Output is correct
8 Correct 159 ms 46928 KB Output is correct
9 Correct 114 ms 46912 KB Output is correct
10 Correct 123 ms 45528 KB Output is correct
11 Correct 125 ms 45092 KB Output is correct
12 Correct 117 ms 46400 KB Output is correct
13 Correct 40 ms 37080 KB Output is correct
14 Correct 138 ms 48068 KB Output is correct
15 Correct 165 ms 46660 KB Output is correct
16 Correct 198 ms 46200 KB Output is correct
17 Correct 21 ms 35656 KB Output is correct
18 Correct 123 ms 46404 KB Output is correct
19 Correct 125 ms 46568 KB Output is correct
20 Correct 117 ms 46916 KB Output is correct
21 Correct 97 ms 46784 KB Output is correct
22 Correct 114 ms 45528 KB Output is correct
23 Correct 101 ms 44968 KB Output is correct
24 Correct 122 ms 46416 KB Output is correct
25 Correct 2520 ms 99336 KB Output is correct
26 Correct 2329 ms 104304 KB Output is correct
27 Correct 2066 ms 101176 KB Output is correct
28 Correct 1520 ms 105548 KB Output is correct
29 Correct 2302 ms 93240 KB Output is correct
30 Correct 2411 ms 89308 KB Output is correct
31 Correct 2497 ms 98252 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37096 KB Output is correct
2 Correct 127 ms 48164 KB Output is correct
3 Correct 125 ms 46680 KB Output is correct
4 Correct 206 ms 46148 KB Output is correct
5 Correct 22 ms 35596 KB Output is correct
6 Correct 121 ms 46372 KB Output is correct
7 Correct 123 ms 46536 KB Output is correct
8 Correct 159 ms 46928 KB Output is correct
9 Correct 114 ms 46912 KB Output is correct
10 Correct 123 ms 45528 KB Output is correct
11 Correct 125 ms 45092 KB Output is correct
12 Correct 117 ms 46400 KB Output is correct
13 Correct 40 ms 37080 KB Output is correct
14 Correct 138 ms 48068 KB Output is correct
15 Correct 165 ms 46660 KB Output is correct
16 Correct 198 ms 46200 KB Output is correct
17 Correct 21 ms 35656 KB Output is correct
18 Correct 123 ms 46404 KB Output is correct
19 Correct 125 ms 46568 KB Output is correct
20 Correct 117 ms 46916 KB Output is correct
21 Correct 97 ms 46784 KB Output is correct
22 Correct 114 ms 45528 KB Output is correct
23 Correct 101 ms 44968 KB Output is correct
24 Correct 122 ms 46416 KB Output is correct
25 Correct 2520 ms 99336 KB Output is correct
26 Correct 2329 ms 104304 KB Output is correct
27 Correct 2066 ms 101176 KB Output is correct
28 Correct 1520 ms 105548 KB Output is correct
29 Correct 2302 ms 93240 KB Output is correct
30 Correct 2411 ms 89308 KB Output is correct
31 Correct 2497 ms 98252 KB Output is correct
32 Correct 39 ms 37028 KB Output is correct
33 Correct 120 ms 48072 KB Output is correct
34 Correct 113 ms 46644 KB Output is correct
35 Correct 193 ms 46148 KB Output is correct
36 Correct 24 ms 35592 KB Output is correct
37 Correct 125 ms 46412 KB Output is correct
38 Correct 102 ms 46664 KB Output is correct
39 Correct 120 ms 46824 KB Output is correct
40 Correct 109 ms 46856 KB Output is correct
41 Correct 128 ms 45508 KB Output is correct
42 Correct 95 ms 45044 KB Output is correct
43 Correct 108 ms 46404 KB Output is correct
44 Correct 2296 ms 94596 KB Output is correct
45 Correct 2259 ms 99792 KB Output is correct
46 Correct 2270 ms 96572 KB Output is correct
47 Correct 1632 ms 100716 KB Output is correct
48 Correct 2277 ms 88308 KB Output is correct
49 Correct 2460 ms 89540 KB Output is correct
50 Correct 2540 ms 98360 KB Output is correct
51 Correct 2873 ms 115512 KB Output is correct
52 Correct 3177 ms 136244 KB Output is correct
53 Correct 2672 ms 117956 KB Output is correct
54 Correct 1499 ms 94020 KB Output is correct
55 Execution timed out 6067 ms 111164 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37072 KB Output is correct
2 Correct 112 ms 48132 KB Output is correct
3 Correct 127 ms 46656 KB Output is correct
4 Correct 181 ms 46264 KB Output is correct
5 Correct 21 ms 35648 KB Output is correct
6 Correct 101 ms 46396 KB Output is correct
7 Correct 41 ms 37096 KB Output is correct
8 Correct 127 ms 48164 KB Output is correct
9 Correct 125 ms 46680 KB Output is correct
10 Correct 206 ms 46148 KB Output is correct
11 Correct 22 ms 35596 KB Output is correct
12 Correct 121 ms 46372 KB Output is correct
13 Correct 123 ms 46536 KB Output is correct
14 Correct 159 ms 46928 KB Output is correct
15 Correct 114 ms 46912 KB Output is correct
16 Correct 123 ms 45528 KB Output is correct
17 Correct 125 ms 45092 KB Output is correct
18 Correct 117 ms 46400 KB Output is correct
19 Correct 23 ms 35532 KB Output is correct
20 Correct 23 ms 35524 KB Output is correct
21 Correct 25 ms 35456 KB Output is correct
22 Correct 43 ms 37044 KB Output is correct
23 Correct 118 ms 48092 KB Output is correct
24 Correct 133 ms 46700 KB Output is correct
25 Correct 200 ms 46252 KB Output is correct
26 Correct 21 ms 35532 KB Output is correct
27 Correct 123 ms 46428 KB Output is correct
28 Correct 104 ms 46500 KB Output is correct
29 Correct 126 ms 46868 KB Output is correct
30 Correct 120 ms 46912 KB Output is correct
31 Correct 135 ms 45512 KB Output is correct
32 Correct 103 ms 45048 KB Output is correct
33 Correct 145 ms 46404 KB Output is correct
34 Correct 2673 ms 98724 KB Output is correct
35 Correct 2682 ms 93956 KB Output is correct
36 Correct 2671 ms 95884 KB Output is correct
37 Correct 2135 ms 101176 KB Output is correct
38 Correct 2364 ms 94020 KB Output is correct
39 Correct 2227 ms 88112 KB Output is correct
40 Correct 2399 ms 88432 KB Output is correct
41 Correct 2526 ms 88072 KB Output is correct
42 Correct 2651 ms 93836 KB Output is correct
43 Correct 2793 ms 93744 KB Output is correct
44 Correct 2761 ms 96716 KB Output is correct
45 Incorrect 1776 ms 85936 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37072 KB Output is correct
2 Correct 112 ms 48132 KB Output is correct
3 Correct 127 ms 46656 KB Output is correct
4 Correct 181 ms 46264 KB Output is correct
5 Correct 21 ms 35648 KB Output is correct
6 Correct 101 ms 46396 KB Output is correct
7 Correct 41 ms 37096 KB Output is correct
8 Correct 127 ms 48164 KB Output is correct
9 Correct 125 ms 46680 KB Output is correct
10 Correct 206 ms 46148 KB Output is correct
11 Correct 22 ms 35596 KB Output is correct
12 Correct 121 ms 46372 KB Output is correct
13 Correct 123 ms 46536 KB Output is correct
14 Correct 159 ms 46928 KB Output is correct
15 Correct 114 ms 46912 KB Output is correct
16 Correct 123 ms 45528 KB Output is correct
17 Correct 125 ms 45092 KB Output is correct
18 Correct 117 ms 46400 KB Output is correct
19 Correct 40 ms 37080 KB Output is correct
20 Correct 138 ms 48068 KB Output is correct
21 Correct 165 ms 46660 KB Output is correct
22 Correct 198 ms 46200 KB Output is correct
23 Correct 21 ms 35656 KB Output is correct
24 Correct 123 ms 46404 KB Output is correct
25 Correct 125 ms 46568 KB Output is correct
26 Correct 117 ms 46916 KB Output is correct
27 Correct 97 ms 46784 KB Output is correct
28 Correct 114 ms 45528 KB Output is correct
29 Correct 101 ms 44968 KB Output is correct
30 Correct 122 ms 46416 KB Output is correct
31 Correct 2520 ms 99336 KB Output is correct
32 Correct 2329 ms 104304 KB Output is correct
33 Correct 2066 ms 101176 KB Output is correct
34 Correct 1520 ms 105548 KB Output is correct
35 Correct 2302 ms 93240 KB Output is correct
36 Correct 2411 ms 89308 KB Output is correct
37 Correct 2497 ms 98252 KB Output is correct
38 Correct 23 ms 35532 KB Output is correct
39 Correct 23 ms 35524 KB Output is correct
40 Correct 25 ms 35456 KB Output is correct
41 Correct 43 ms 37044 KB Output is correct
42 Correct 118 ms 48092 KB Output is correct
43 Correct 133 ms 46700 KB Output is correct
44 Correct 200 ms 46252 KB Output is correct
45 Correct 21 ms 35532 KB Output is correct
46 Correct 123 ms 46428 KB Output is correct
47 Correct 104 ms 46500 KB Output is correct
48 Correct 126 ms 46868 KB Output is correct
49 Correct 120 ms 46912 KB Output is correct
50 Correct 135 ms 45512 KB Output is correct
51 Correct 103 ms 45048 KB Output is correct
52 Correct 145 ms 46404 KB Output is correct
53 Correct 2673 ms 98724 KB Output is correct
54 Correct 2682 ms 93956 KB Output is correct
55 Correct 2671 ms 95884 KB Output is correct
56 Correct 2135 ms 101176 KB Output is correct
57 Correct 2364 ms 94020 KB Output is correct
58 Correct 2227 ms 88112 KB Output is correct
59 Correct 2399 ms 88432 KB Output is correct
60 Correct 2526 ms 88072 KB Output is correct
61 Correct 2651 ms 93836 KB Output is correct
62 Correct 2793 ms 93744 KB Output is correct
63 Correct 2761 ms 96716 KB Output is correct
64 Incorrect 1776 ms 85936 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37072 KB Output is correct
2 Correct 112 ms 48132 KB Output is correct
3 Correct 127 ms 46656 KB Output is correct
4 Correct 181 ms 46264 KB Output is correct
5 Correct 21 ms 35648 KB Output is correct
6 Correct 101 ms 46396 KB Output is correct
7 Correct 41 ms 37096 KB Output is correct
8 Correct 127 ms 48164 KB Output is correct
9 Correct 125 ms 46680 KB Output is correct
10 Correct 206 ms 46148 KB Output is correct
11 Correct 22 ms 35596 KB Output is correct
12 Correct 121 ms 46372 KB Output is correct
13 Correct 123 ms 46536 KB Output is correct
14 Correct 159 ms 46928 KB Output is correct
15 Correct 114 ms 46912 KB Output is correct
16 Correct 123 ms 45528 KB Output is correct
17 Correct 125 ms 45092 KB Output is correct
18 Correct 117 ms 46400 KB Output is correct
19 Correct 40 ms 37080 KB Output is correct
20 Correct 138 ms 48068 KB Output is correct
21 Correct 165 ms 46660 KB Output is correct
22 Correct 198 ms 46200 KB Output is correct
23 Correct 21 ms 35656 KB Output is correct
24 Correct 123 ms 46404 KB Output is correct
25 Correct 125 ms 46568 KB Output is correct
26 Correct 117 ms 46916 KB Output is correct
27 Correct 97 ms 46784 KB Output is correct
28 Correct 114 ms 45528 KB Output is correct
29 Correct 101 ms 44968 KB Output is correct
30 Correct 122 ms 46416 KB Output is correct
31 Correct 2520 ms 99336 KB Output is correct
32 Correct 2329 ms 104304 KB Output is correct
33 Correct 2066 ms 101176 KB Output is correct
34 Correct 1520 ms 105548 KB Output is correct
35 Correct 2302 ms 93240 KB Output is correct
36 Correct 2411 ms 89308 KB Output is correct
37 Correct 2497 ms 98252 KB Output is correct
38 Correct 39 ms 37028 KB Output is correct
39 Correct 120 ms 48072 KB Output is correct
40 Correct 113 ms 46644 KB Output is correct
41 Correct 193 ms 46148 KB Output is correct
42 Correct 24 ms 35592 KB Output is correct
43 Correct 125 ms 46412 KB Output is correct
44 Correct 102 ms 46664 KB Output is correct
45 Correct 120 ms 46824 KB Output is correct
46 Correct 109 ms 46856 KB Output is correct
47 Correct 128 ms 45508 KB Output is correct
48 Correct 95 ms 45044 KB Output is correct
49 Correct 108 ms 46404 KB Output is correct
50 Correct 2296 ms 94596 KB Output is correct
51 Correct 2259 ms 99792 KB Output is correct
52 Correct 2270 ms 96572 KB Output is correct
53 Correct 1632 ms 100716 KB Output is correct
54 Correct 2277 ms 88308 KB Output is correct
55 Correct 2460 ms 89540 KB Output is correct
56 Correct 2540 ms 98360 KB Output is correct
57 Correct 2873 ms 115512 KB Output is correct
58 Correct 3177 ms 136244 KB Output is correct
59 Correct 2672 ms 117956 KB Output is correct
60 Correct 1499 ms 94020 KB Output is correct
61 Execution timed out 6067 ms 111164 KB Time limit exceeded
62 Halted 0 ms 0 KB -