oj.uz

Submission #425946

# Submission time Handle Problem Language Result Execution time Memory
425946 2021-06-13T12:31:44 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
0 / 100
 6000 ms 131300 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];
int dist[250000];
priority_queue<pii> H;
set<pii> seen;
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++) dist[i] = 1e9;
    dist[0] = 0,H.push(mp(0,0));
    while (!H.empty()) {
        int u = H.top().second;
        int d = -H.top().first;
        H.pop();
        if (seen.count(mp(u,d))) continue;
        seen.insert(mp(u,d));

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

    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3781 ms 9384 KB Output is correct
2 Execution timed out 6054 ms 130200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3636 ms 9460 KB Output is correct
2 Execution timed out 6102 ms 131300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3636 ms 9460 KB Output is correct
2 Execution timed out 6102 ms 131300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3636 ms 9460 KB Output is correct
2 Execution timed out 6102 ms 131300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3781 ms 9384 KB Output is correct
2 Execution timed out 6054 ms 130200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3781 ms 9384 KB Output is correct
2 Execution timed out 6054 ms 130200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3781 ms 9384 KB Output is correct
2 Execution timed out 6054 ms 130200 KB Time limit exceeded
3 Halted 0 ms 0 KB -