oj.uz

Submission #400944

# Submission time Handle Problem Language Result Execution time Memory
400944 2021-05-08T21:32:34 Z 534351 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 173280 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 = 69;

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];
pii ban[MAXN];
unordered_map<int, pii> banedge[MAXN];
int dist[MAXN];
bitset<DELTA + 3> seen[MAXN];
priority_queue<pii, vector<pii>, greater<pii> > pq;

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);
    }
    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, c};
        }
        FOR(j, 0, c)
        {
            int u = s[j], v = s[(j == c - 1 ? 0 : j + 1)];
            banedge[u][v] = {j, c};
            banedge[v][u] = {j, c};
            // cerr << u << ' ' << v << ' ' << j << ' ' << c << endl;
        }
    }
    fill(dist, dist + N, INF);
    dist[0] = 0;
    pq.push({0, 0});
    while(!pq.empty())
    {
        int d = pq.top().fi, u = pq.top().se; pq.pop();
        if (d - dist[u] >= DELTA) continue;
        // cerr << d << ' ' << u << endl;
        if (seen[u][d - dist[u]]) continue;
        seen[u][d - dist[u]] = true;
        for (int v : edge[u])
        {
            if (ban[v].se != 0 && (d + 1) % ban[v].se == ban[v].fi) continue;
            if (banedge[u].count(v) && d % banedge[u][v].se == banedge[u][v].fi) continue;
            if (dist[v] > d + 1)
            {
                dist[v] = d + 1;
            }
            // cerr << u << ' ' << v << ' ' << d + 1 << endl;
            pq.push({d + 1, v});
            //you can go from u -> v at time t iff:
            //t != ban[v].fi mod ban[v].se
            //t-1 != ban[u][v].fi mod ban[u][v].se
        }
    }
    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 1863 ms 22984 KB Output is correct
2 Correct 2189 ms 25364 KB Output is correct
3 Correct 2774 ms 27336 KB Output is correct
4 Correct 3309 ms 28312 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2957 ms 27324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1854 ms 22976 KB Output is correct
2 Correct 2190 ms 25412 KB Output is correct
3 Correct 2783 ms 27344 KB Output is correct
4 Correct 3357 ms 28348 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2968 ms 27288 KB Output is correct
7 Correct 2580 ms 27040 KB Output is correct
8 Correct 2487 ms 26944 KB Output is correct
9 Correct 2296 ms 26816 KB Output is correct
10 Correct 3111 ms 27184 KB Output is correct
11 Correct 3245 ms 26672 KB Output is correct
12 Correct 2939 ms 27324 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1854 ms 22976 KB Output is correct
2 Correct 2190 ms 25412 KB Output is correct
3 Correct 2783 ms 27344 KB Output is correct
4 Correct 3357 ms 28348 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2968 ms 27288 KB Output is correct
7 Correct 2580 ms 27040 KB Output is correct
8 Correct 2487 ms 26944 KB Output is correct
9 Correct 2296 ms 26816 KB Output is correct
10 Correct 3111 ms 27184 KB Output is correct
11 Correct 3245 ms 26672 KB Output is correct
12 Correct 2939 ms 27324 KB Output is correct
13 Correct 1857 ms 23548 KB Output is correct
14 Correct 2202 ms 26436 KB Output is correct
15 Correct 2816 ms 27320 KB Output is correct
16 Correct 3287 ms 28328 KB Output is correct
17 Correct 15 ms 19916 KB Output is correct
18 Correct 2982 ms 27324 KB Output is correct
19 Correct 2561 ms 26824 KB Output is correct
20 Correct 2456 ms 26820 KB Output is correct
21 Correct 2303 ms 26816 KB Output is correct
22 Correct 3078 ms 27244 KB Output is correct
23 Correct 3238 ms 26684 KB Output is correct
24 Correct 2937 ms 27376 KB Output is correct
25 Execution timed out 6091 ms 172692 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1854 ms 22976 KB Output is correct
2 Correct 2190 ms 25412 KB Output is correct
3 Correct 2783 ms 27344 KB Output is correct
4 Correct 3357 ms 28348 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2968 ms 27288 KB Output is correct
7 Correct 2580 ms 27040 KB Output is correct
8 Correct 2487 ms 26944 KB Output is correct
9 Correct 2296 ms 26816 KB Output is correct
10 Correct 3111 ms 27184 KB Output is correct
11 Correct 3245 ms 26672 KB Output is correct
12 Correct 2939 ms 27324 KB Output is correct
13 Correct 1857 ms 23548 KB Output is correct
14 Correct 2202 ms 26436 KB Output is correct
15 Correct 2816 ms 27320 KB Output is correct
16 Correct 3287 ms 28328 KB Output is correct
17 Correct 15 ms 19916 KB Output is correct
18 Correct 2982 ms 27324 KB Output is correct
19 Correct 2561 ms 26824 KB Output is correct
20 Correct 2456 ms 26820 KB Output is correct
21 Correct 2303 ms 26816 KB Output is correct
22 Correct 3078 ms 27244 KB Output is correct
23 Correct 3238 ms 26684 KB Output is correct
24 Correct 2937 ms 27376 KB Output is correct
25 Execution timed out 6091 ms 172692 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 22984 KB Output is correct
2 Correct 2189 ms 25364 KB Output is correct
3 Correct 2774 ms 27336 KB Output is correct
4 Correct 3309 ms 28312 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2957 ms 27324 KB Output is correct
7 Correct 1854 ms 22976 KB Output is correct
8 Correct 2190 ms 25412 KB Output is correct
9 Correct 2783 ms 27344 KB Output is correct
10 Correct 3357 ms 28348 KB Output is correct
11 Correct 15 ms 19916 KB Output is correct
12 Correct 2968 ms 27288 KB Output is correct
13 Correct 2580 ms 27040 KB Output is correct
14 Correct 2487 ms 26944 KB Output is correct
15 Correct 2296 ms 26816 KB Output is correct
16 Correct 3111 ms 27184 KB Output is correct
17 Correct 3245 ms 26672 KB Output is correct
18 Correct 2939 ms 27324 KB Output is correct
19 Correct 14 ms 19828 KB Output is correct
20 Correct 13 ms 19904 KB Output is correct
21 Correct 13 ms 19916 KB Output is correct
22 Correct 1848 ms 23540 KB Output is correct
23 Correct 2184 ms 26564 KB Output is correct
24 Correct 2784 ms 27452 KB Output is correct
25 Correct 3328 ms 28340 KB Output is correct
26 Correct 15 ms 19916 KB Output is correct
27 Correct 2961 ms 27292 KB Output is correct
28 Correct 2565 ms 26720 KB Output is correct
29 Correct 2486 ms 26816 KB Output is correct
30 Correct 2305 ms 26816 KB Output is correct
31 Correct 3140 ms 27204 KB Output is correct
32 Correct 3283 ms 26688 KB Output is correct
33 Correct 2964 ms 27320 KB Output is correct
34 Execution timed out 6057 ms 173280 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 22984 KB Output is correct
2 Correct 2189 ms 25364 KB Output is correct
3 Correct 2774 ms 27336 KB Output is correct
4 Correct 3309 ms 28312 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2957 ms 27324 KB Output is correct
7 Correct 1854 ms 22976 KB Output is correct
8 Correct 2190 ms 25412 KB Output is correct
9 Correct 2783 ms 27344 KB Output is correct
10 Correct 3357 ms 28348 KB Output is correct
11 Correct 15 ms 19916 KB Output is correct
12 Correct 2968 ms 27288 KB Output is correct
13 Correct 2580 ms 27040 KB Output is correct
14 Correct 2487 ms 26944 KB Output is correct
15 Correct 2296 ms 26816 KB Output is correct
16 Correct 3111 ms 27184 KB Output is correct
17 Correct 3245 ms 26672 KB Output is correct
18 Correct 2939 ms 27324 KB Output is correct
19 Correct 1857 ms 23548 KB Output is correct
20 Correct 2202 ms 26436 KB Output is correct
21 Correct 2816 ms 27320 KB Output is correct
22 Correct 3287 ms 28328 KB Output is correct
23 Correct 15 ms 19916 KB Output is correct
24 Correct 2982 ms 27324 KB Output is correct
25 Correct 2561 ms 26824 KB Output is correct
26 Correct 2456 ms 26820 KB Output is correct
27 Correct 2303 ms 26816 KB Output is correct
28 Correct 3078 ms 27244 KB Output is correct
29 Correct 3238 ms 26684 KB Output is correct
30 Correct 2937 ms 27376 KB Output is correct
31 Execution timed out 6091 ms 172692 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 22984 KB Output is correct
2 Correct 2189 ms 25364 KB Output is correct
3 Correct 2774 ms 27336 KB Output is correct
4 Correct 3309 ms 28312 KB Output is correct
5 Correct 15 ms 19916 KB Output is correct
6 Correct 2957 ms 27324 KB Output is correct
7 Correct 1854 ms 22976 KB Output is correct
8 Correct 2190 ms 25412 KB Output is correct
9 Correct 2783 ms 27344 KB Output is correct
10 Correct 3357 ms 28348 KB Output is correct
11 Correct 15 ms 19916 KB Output is correct
12 Correct 2968 ms 27288 KB Output is correct
13 Correct 2580 ms 27040 KB Output is correct
14 Correct 2487 ms 26944 KB Output is correct
15 Correct 2296 ms 26816 KB Output is correct
16 Correct 3111 ms 27184 KB Output is correct
17 Correct 3245 ms 26672 KB Output is correct
18 Correct 2939 ms 27324 KB Output is correct
19 Correct 1857 ms 23548 KB Output is correct
20 Correct 2202 ms 26436 KB Output is correct
21 Correct 2816 ms 27320 KB Output is correct
22 Correct 3287 ms 28328 KB Output is correct
23 Correct 15 ms 19916 KB Output is correct
24 Correct 2982 ms 27324 KB Output is correct
25 Correct 2561 ms 26824 KB Output is correct
26 Correct 2456 ms 26820 KB Output is correct
27 Correct 2303 ms 26816 KB Output is correct
28 Correct 3078 ms 27244 KB Output is correct
29 Correct 3238 ms 26684 KB Output is correct
30 Correct 2937 ms 27376 KB Output is correct
31 Execution timed out 6091 ms 172692 KB Time limit exceeded
32 Halted 0 ms 0 KB -