oj.uz

Submission #400952

# Submission time Handle Problem Language Result Execution time Memory
400952 2021-05-08T21:55:28 Z 534351 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 57676 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 250013;
const int INF = 1e9 + 7;
const int DELTA = 88;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, K;
vi edge[MAXN];
int ban[MAXN], md[MAXN];
int dist[MAXN], cc[MAXN];
bitset<DELTA + 3> seen[MAXN];
queue<pii> q;

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    FOR(i, 0, M)
    {
        int u, v;
        cin >> u >> v; u--; v--;
        edge[u].PB(v);
        edge[v].PB(u);
    }
    FOR(i, 0, N)
    {
        edge[i].PB(i);
        cc[i] = -1;
    }
    cin >> K;
    FOR(i, 0, K)
    {
        int c; cin >> c;
        vi s(c);
        FOR(j, 0, c)
        {
            cin >> s[j]; s[j]--;
            ban[s[j]] = j;
            cc[s[j]] = i;
        }
        md[i] = c;
    }
    fill(dist, dist + N, INF);
    dist[0] = 0;
    seen[0][0] = true;
    q.push({0, 0});
    while(!q.empty())
    {
        int d = q.front().fi, u = q.front().se; q.pop();
        if (u == N - 1) break;
        for (int v : edge[u])
        {
            if (cc[v] != -1)
            {
                int m = md[cc[v]];
                if ((d + 1) % m == ban[v]) continue;
                if (cc[u] == cc[v] && (d + 1) % m == ban[u] && d % m == ban[v]) continue;
            }
            if (dist[v] > d + 1)
            {
                dist[v] = d + 1;
            }
            if (d + 1 - dist[v] >= DELTA || seen[v][d + 1 - dist[v]]) continue;
            seen[v][d + 1 - dist[v]] = true;
            q.push({d + 1, v});
        }
    }
    if (dist[N - 1] >= INF)
    {
        cout << "impossible\n";
        return 0;
    }
    cout << dist[N - 1] << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7056 KB Output is correct
2 Correct 447 ms 12012 KB Output is correct
3 Correct 524 ms 11720 KB Output is correct
4 Correct 815 ms 11956 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 609 ms 11816 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7116 KB Output is correct
2 Correct 448 ms 11948 KB Output is correct
3 Correct 524 ms 11812 KB Output is correct
4 Correct 754 ms 11844 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 612 ms 11844 KB Output is correct
7 Correct 483 ms 11752 KB Output is correct
8 Correct 459 ms 11712 KB Output is correct
9 Correct 455 ms 11588 KB Output is correct
10 Correct 649 ms 11844 KB Output is correct
11 Correct 719 ms 11716 KB Output is correct
12 Correct 550 ms 11844 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7116 KB Output is correct
2 Correct 448 ms 11948 KB Output is correct
3 Correct 524 ms 11812 KB Output is correct
4 Correct 754 ms 11844 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 612 ms 11844 KB Output is correct
7 Correct 483 ms 11752 KB Output is correct
8 Correct 459 ms 11712 KB Output is correct
9 Correct 455 ms 11588 KB Output is correct
10 Correct 649 ms 11844 KB Output is correct
11 Correct 719 ms 11716 KB Output is correct
12 Correct 550 ms 11844 KB Output is correct
13 Correct 19 ms 7036 KB Output is correct
14 Correct 462 ms 12080 KB Output is correct
15 Correct 534 ms 11844 KB Output is correct
16 Correct 749 ms 11968 KB Output is correct
17 Correct 4 ms 6220 KB Output is correct
18 Correct 619 ms 11760 KB Output is correct
19 Correct 481 ms 11716 KB Output is correct
20 Correct 458 ms 11588 KB Output is correct
21 Correct 464 ms 11604 KB Output is correct
22 Correct 618 ms 11808 KB Output is correct
23 Correct 716 ms 11716 KB Output is correct
24 Correct 549 ms 11864 KB Output is correct
25 Execution timed out 6060 ms 56572 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7116 KB Output is correct
2 Correct 448 ms 11948 KB Output is correct
3 Correct 524 ms 11812 KB Output is correct
4 Correct 754 ms 11844 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 612 ms 11844 KB Output is correct
7 Correct 483 ms 11752 KB Output is correct
8 Correct 459 ms 11712 KB Output is correct
9 Correct 455 ms 11588 KB Output is correct
10 Correct 649 ms 11844 KB Output is correct
11 Correct 719 ms 11716 KB Output is correct
12 Correct 550 ms 11844 KB Output is correct
13 Correct 19 ms 7036 KB Output is correct
14 Correct 462 ms 12080 KB Output is correct
15 Correct 534 ms 11844 KB Output is correct
16 Correct 749 ms 11968 KB Output is correct
17 Correct 4 ms 6220 KB Output is correct
18 Correct 619 ms 11760 KB Output is correct
19 Correct 481 ms 11716 KB Output is correct
20 Correct 458 ms 11588 KB Output is correct
21 Correct 464 ms 11604 KB Output is correct
22 Correct 618 ms 11808 KB Output is correct
23 Correct 716 ms 11716 KB Output is correct
24 Correct 549 ms 11864 KB Output is correct
25 Execution timed out 6060 ms 56572 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7056 KB Output is correct
2 Correct 447 ms 12012 KB Output is correct
3 Correct 524 ms 11720 KB Output is correct
4 Correct 815 ms 11956 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 609 ms 11816 KB Output is correct
7 Correct 18 ms 7116 KB Output is correct
8 Correct 448 ms 11948 KB Output is correct
9 Correct 524 ms 11812 KB Output is correct
10 Correct 754 ms 11844 KB Output is correct
11 Correct 4 ms 6220 KB Output is correct
12 Correct 612 ms 11844 KB Output is correct
13 Correct 483 ms 11752 KB Output is correct
14 Correct 459 ms 11712 KB Output is correct
15 Correct 455 ms 11588 KB Output is correct
16 Correct 649 ms 11844 KB Output is correct
17 Correct 719 ms 11716 KB Output is correct
18 Correct 550 ms 11844 KB Output is correct
19 Correct 4 ms 6092 KB Output is correct
20 Correct 4 ms 6092 KB Output is correct
21 Correct 4 ms 6092 KB Output is correct
22 Correct 19 ms 7116 KB Output is correct
23 Correct 442 ms 11956 KB Output is correct
24 Correct 538 ms 11716 KB Output is correct
25 Correct 792 ms 11968 KB Output is correct
26 Correct 4 ms 6220 KB Output is correct
27 Correct 625 ms 11972 KB Output is correct
28 Correct 477 ms 11716 KB Output is correct
29 Correct 471 ms 11704 KB Output is correct
30 Correct 457 ms 11588 KB Output is correct
31 Correct 621 ms 11716 KB Output is correct
32 Correct 701 ms 11716 KB Output is correct
33 Correct 582 ms 11868 KB Output is correct
34 Execution timed out 6042 ms 57676 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7056 KB Output is correct
2 Correct 447 ms 12012 KB Output is correct
3 Correct 524 ms 11720 KB Output is correct
4 Correct 815 ms 11956 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 609 ms 11816 KB Output is correct
7 Correct 18 ms 7116 KB Output is correct
8 Correct 448 ms 11948 KB Output is correct
9 Correct 524 ms 11812 KB Output is correct
10 Correct 754 ms 11844 KB Output is correct
11 Correct 4 ms 6220 KB Output is correct
12 Correct 612 ms 11844 KB Output is correct
13 Correct 483 ms 11752 KB Output is correct
14 Correct 459 ms 11712 KB Output is correct
15 Correct 455 ms 11588 KB Output is correct
16 Correct 649 ms 11844 KB Output is correct
17 Correct 719 ms 11716 KB Output is correct
18 Correct 550 ms 11844 KB Output is correct
19 Correct 19 ms 7036 KB Output is correct
20 Correct 462 ms 12080 KB Output is correct
21 Correct 534 ms 11844 KB Output is correct
22 Correct 749 ms 11968 KB Output is correct
23 Correct 4 ms 6220 KB Output is correct
24 Correct 619 ms 11760 KB Output is correct
25 Correct 481 ms 11716 KB Output is correct
26 Correct 458 ms 11588 KB Output is correct
27 Correct 464 ms 11604 KB Output is correct
28 Correct 618 ms 11808 KB Output is correct
29 Correct 716 ms 11716 KB Output is correct
30 Correct 549 ms 11864 KB Output is correct
31 Execution timed out 6060 ms 56572 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7056 KB Output is correct
2 Correct 447 ms 12012 KB Output is correct
3 Correct 524 ms 11720 KB Output is correct
4 Correct 815 ms 11956 KB Output is correct
5 Correct 4 ms 6220 KB Output is correct
6 Correct 609 ms 11816 KB Output is correct
7 Correct 18 ms 7116 KB Output is correct
8 Correct 448 ms 11948 KB Output is correct
9 Correct 524 ms 11812 KB Output is correct
10 Correct 754 ms 11844 KB Output is correct
11 Correct 4 ms 6220 KB Output is correct
12 Correct 612 ms 11844 KB Output is correct
13 Correct 483 ms 11752 KB Output is correct
14 Correct 459 ms 11712 KB Output is correct
15 Correct 455 ms 11588 KB Output is correct
16 Correct 649 ms 11844 KB Output is correct
17 Correct 719 ms 11716 KB Output is correct
18 Correct 550 ms 11844 KB Output is correct
19 Correct 19 ms 7036 KB Output is correct
20 Correct 462 ms 12080 KB Output is correct
21 Correct 534 ms 11844 KB Output is correct
22 Correct 749 ms 11968 KB Output is correct
23 Correct 4 ms 6220 KB Output is correct
24 Correct 619 ms 11760 KB Output is correct
25 Correct 481 ms 11716 KB Output is correct
26 Correct 458 ms 11588 KB Output is correct
27 Correct 464 ms 11604 KB Output is correct
28 Correct 618 ms 11808 KB Output is correct
29 Correct 716 ms 11716 KB Output is correct
30 Correct 549 ms 11864 KB Output is correct
31 Execution timed out 6060 ms 56572 KB Time limit exceeded
32 Halted 0 ms 0 KB -