oj.uz

Submission #426015

# Submission time Handle Problem Language Result Execution time Memory
426015 2021-06-13T13:00:20 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
15 / 100
 6000 ms 66912 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;

vi adjList[250000];
pair<int,pii> p[250000];
vi dist[250000];
priority_queue<pii> H;
int main() {
    int i,j;
    int N,M,K;
    int u,v,l;
    scanf("%d %d",&N,&M);
    for (i = 0; i < M; i++) {
        scanf("%d %d",&u,&v);
        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);
    }
    dist[0][0] = 0,H.push(mp(0,0));
    while (!H.empty()) {
        int u = H.top().second;
        int d = -H.top().first;
        H.pop();

        if (d > dist[u][d % p[u].first]) continue;
        else if (u == N-1) {
            printf("%d\n",d);
            return 0;
        }
        for (i = 0; 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++) {
                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;
                        H.push(mp(-(d+1),v));
                    }
                }
                d++;
                if ((p[u].first != 1) && ((d % p[u].first) == p[u].second.first)) break;
            }
            d = t;
        }
    }
    printf("impossible\n");

    return 0;
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (i = 0; i < adjList[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d",&l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:28:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         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 28 ms 13380 KB Output is correct
2 Correct 126 ms 19776 KB Output is correct
3 Correct 121 ms 19292 KB Output is correct
4 Correct 214 ms 19560 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 122 ms 19304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13388 KB Output is correct
2 Correct 101 ms 19700 KB Output is correct
3 Correct 100 ms 19232 KB Output is correct
4 Correct 202 ms 19496 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 157 ms 19300 KB Output is correct
7 Correct 117 ms 19036 KB Output is correct
8 Correct 115 ms 19040 KB Output is correct
9 Correct 115 ms 19052 KB Output is correct
10 Correct 137 ms 19228 KB Output is correct
11 Correct 98 ms 19092 KB Output is correct
12 Correct 135 ms 19012 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13388 KB Output is correct
2 Correct 101 ms 19700 KB Output is correct
3 Correct 100 ms 19232 KB Output is correct
4 Correct 202 ms 19496 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 157 ms 19300 KB Output is correct
7 Correct 117 ms 19036 KB Output is correct
8 Correct 115 ms 19040 KB Output is correct
9 Correct 115 ms 19052 KB Output is correct
10 Correct 137 ms 19228 KB Output is correct
11 Correct 98 ms 19092 KB Output is correct
12 Correct 135 ms 19012 KB Output is correct
13 Correct 29 ms 13480 KB Output is correct
14 Correct 106 ms 19768 KB Output is correct
15 Correct 128 ms 19280 KB Output is correct
16 Correct 199 ms 19484 KB Output is correct
17 Correct 8 ms 12108 KB Output is correct
18 Correct 163 ms 19224 KB Output is correct
19 Correct 97 ms 19028 KB Output is correct
20 Correct 135 ms 19140 KB Output is correct
21 Correct 98 ms 19136 KB Output is correct
22 Correct 168 ms 19280 KB Output is correct
23 Correct 120 ms 19064 KB Output is correct
24 Correct 135 ms 19060 KB Output is correct
25 Correct 2802 ms 62716 KB Output is correct
26 Correct 2861 ms 66912 KB Output is correct
27 Correct 2853 ms 62900 KB Output is correct
28 Correct 1674 ms 66772 KB Output is correct
29 Execution timed out 6097 ms 59092 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13388 KB Output is correct
2 Correct 101 ms 19700 KB Output is correct
3 Correct 100 ms 19232 KB Output is correct
4 Correct 202 ms 19496 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 157 ms 19300 KB Output is correct
7 Correct 117 ms 19036 KB Output is correct
8 Correct 115 ms 19040 KB Output is correct
9 Correct 115 ms 19052 KB Output is correct
10 Correct 137 ms 19228 KB Output is correct
11 Correct 98 ms 19092 KB Output is correct
12 Correct 135 ms 19012 KB Output is correct
13 Correct 29 ms 13480 KB Output is correct
14 Correct 106 ms 19768 KB Output is correct
15 Correct 128 ms 19280 KB Output is correct
16 Correct 199 ms 19484 KB Output is correct
17 Correct 8 ms 12108 KB Output is correct
18 Correct 163 ms 19224 KB Output is correct
19 Correct 97 ms 19028 KB Output is correct
20 Correct 135 ms 19140 KB Output is correct
21 Correct 98 ms 19136 KB Output is correct
22 Correct 168 ms 19280 KB Output is correct
23 Correct 120 ms 19064 KB Output is correct
24 Correct 135 ms 19060 KB Output is correct
25 Correct 2802 ms 62716 KB Output is correct
26 Correct 2861 ms 66912 KB Output is correct
27 Correct 2853 ms 62900 KB Output is correct
28 Correct 1674 ms 66772 KB Output is correct
29 Execution timed out 6097 ms 59092 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 13380 KB Output is correct
2 Correct 126 ms 19776 KB Output is correct
3 Correct 121 ms 19292 KB Output is correct
4 Correct 214 ms 19560 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 122 ms 19304 KB Output is correct
7 Correct 27 ms 13388 KB Output is correct
8 Correct 101 ms 19700 KB Output is correct
9 Correct 100 ms 19232 KB Output is correct
10 Correct 202 ms 19496 KB Output is correct
11 Correct 9 ms 12108 KB Output is correct
12 Correct 157 ms 19300 KB Output is correct
13 Correct 117 ms 19036 KB Output is correct
14 Correct 115 ms 19040 KB Output is correct
15 Correct 115 ms 19052 KB Output is correct
16 Correct 137 ms 19228 KB Output is correct
17 Correct 98 ms 19092 KB Output is correct
18 Correct 135 ms 19012 KB Output is correct
19 Correct 8 ms 11980 KB Output is correct
20 Correct 9 ms 12044 KB Output is correct
21 Correct 10 ms 11980 KB Output is correct
22 Correct 29 ms 13516 KB Output is correct
23 Correct 146 ms 19896 KB Output is correct
24 Correct 111 ms 19456 KB Output is correct
25 Correct 171 ms 19664 KB Output is correct
26 Correct 11 ms 12108 KB Output is correct
27 Correct 127 ms 19400 KB Output is correct
28 Correct 100 ms 19212 KB Output is correct
29 Correct 103 ms 19212 KB Output is correct
30 Correct 117 ms 19236 KB Output is correct
31 Correct 135 ms 19448 KB Output is correct
32 Correct 103 ms 19296 KB Output is correct
33 Correct 143 ms 19260 KB Output is correct
34 Correct 2792 ms 63416 KB Output is correct
35 Correct 2898 ms 59624 KB Output is correct
36 Correct 2790 ms 59704 KB Output is correct
37 Incorrect 2393 ms 65240 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 13380 KB Output is correct
2 Correct 126 ms 19776 KB Output is correct
3 Correct 121 ms 19292 KB Output is correct
4 Correct 214 ms 19560 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 122 ms 19304 KB Output is correct
7 Correct 27 ms 13388 KB Output is correct
8 Correct 101 ms 19700 KB Output is correct
9 Correct 100 ms 19232 KB Output is correct
10 Correct 202 ms 19496 KB Output is correct
11 Correct 9 ms 12108 KB Output is correct
12 Correct 157 ms 19300 KB Output is correct
13 Correct 117 ms 19036 KB Output is correct
14 Correct 115 ms 19040 KB Output is correct
15 Correct 115 ms 19052 KB Output is correct
16 Correct 137 ms 19228 KB Output is correct
17 Correct 98 ms 19092 KB Output is correct
18 Correct 135 ms 19012 KB Output is correct
19 Correct 29 ms 13480 KB Output is correct
20 Correct 106 ms 19768 KB Output is correct
21 Correct 128 ms 19280 KB Output is correct
22 Correct 199 ms 19484 KB Output is correct
23 Correct 8 ms 12108 KB Output is correct
24 Correct 163 ms 19224 KB Output is correct
25 Correct 97 ms 19028 KB Output is correct
26 Correct 135 ms 19140 KB Output is correct
27 Correct 98 ms 19136 KB Output is correct
28 Correct 168 ms 19280 KB Output is correct
29 Correct 120 ms 19064 KB Output is correct
30 Correct 135 ms 19060 KB Output is correct
31 Correct 2802 ms 62716 KB Output is correct
32 Correct 2861 ms 66912 KB Output is correct
33 Correct 2853 ms 62900 KB Output is correct
34 Correct 1674 ms 66772 KB Output is correct
35 Execution timed out 6097 ms 59092 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 13380 KB Output is correct
2 Correct 126 ms 19776 KB Output is correct
3 Correct 121 ms 19292 KB Output is correct
4 Correct 214 ms 19560 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 122 ms 19304 KB Output is correct
7 Correct 27 ms 13388 KB Output is correct
8 Correct 101 ms 19700 KB Output is correct
9 Correct 100 ms 19232 KB Output is correct
10 Correct 202 ms 19496 KB Output is correct
11 Correct 9 ms 12108 KB Output is correct
12 Correct 157 ms 19300 KB Output is correct
13 Correct 117 ms 19036 KB Output is correct
14 Correct 115 ms 19040 KB Output is correct
15 Correct 115 ms 19052 KB Output is correct
16 Correct 137 ms 19228 KB Output is correct
17 Correct 98 ms 19092 KB Output is correct
18 Correct 135 ms 19012 KB Output is correct
19 Correct 29 ms 13480 KB Output is correct
20 Correct 106 ms 19768 KB Output is correct
21 Correct 128 ms 19280 KB Output is correct
22 Correct 199 ms 19484 KB Output is correct
23 Correct 8 ms 12108 KB Output is correct
24 Correct 163 ms 19224 KB Output is correct
25 Correct 97 ms 19028 KB Output is correct
26 Correct 135 ms 19140 KB Output is correct
27 Correct 98 ms 19136 KB Output is correct
28 Correct 168 ms 19280 KB Output is correct
29 Correct 120 ms 19064 KB Output is correct
30 Correct 135 ms 19060 KB Output is correct
31 Correct 2802 ms 62716 KB Output is correct
32 Correct 2861 ms 66912 KB Output is correct
33 Correct 2853 ms 62900 KB Output is correct
34 Correct 1674 ms 66772 KB Output is correct
35 Execution timed out 6097 ms 59092 KB Time limit exceeded
36 Halted 0 ms 0 KB -