oj.uz

답안 #400962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400962 2021-05-08T22:32:55 Z 534351 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 4336 ms 524292 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 MAXC = 2813;
const int INF = 1e9 + 7;
const int DELTA = 125;

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, B;
vi edge[MAXN];
int ban[MAXN], md[MAXN], id[MAXN], dist[MAXN], cc[MAXN];
bitset<DELTA> seen[MAXC];
priority_queue<pii, vector<pii>, greater<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]--;
            id[s[j]] = B; B++;
            ban[s[j]] = j;
            cc[s[j]] = i;
        }
        md[i] = c;
    }
    fill(dist, dist + N, INF);
    dist[0] = 0;
    q.push({0, 0});
    while(!q.empty())
    {
        int d = q.top().fi, u = q.top().se; q.pop();
        if (u == N - 1) break;
        if (cc[u] != -1)
        {
            if (seen[id[u]][d - dist[u]])
            {
                continue;
            }
            seen[id[u]][d - dist[u]] = true;
        }
        // cerr << d << ' ' << u << endl;
        // bool ok = false;
        // for (int v : edge[u])
        // {
        //     if (!seen[v][0]) ok = true;
        //     //make sure there's one univisited neighbor
        // }
        // if (!ok) continue;
        for (int v : edge[u])
        {
            if (cc[v] != -1)
            {
                FOR(j, 1, (cc[u] == -1 ? DELTA : 2))
                {
                    // cerr << u << ' ' << v << ' ' << (d + j) << endl;
                    int m = md[cc[v]];
                    if ((d + j) % m == ban[v]) continue;
                    if (cc[u] == cc[v] && (d + j) % m == ban[u] && (d + j - 1) % m == ban[v]) continue;
                    if (dist[v] > d + j)
                    {
                        dist[v] = d + j;
                    }
                    if (d + j - dist[v] >= DELTA) continue;
                    q.push({d + j, v});
                }
            }
            else
            {
                if (dist[v] > d + 1)
                {
                    dist[v] = d + 1;
                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 73312 KB Output is correct
2 Correct 63 ms 10956 KB Output is correct
3 Correct 86 ms 11020 KB Output is correct
4 Correct 500 ms 15040 KB Output is correct
5 Correct 6 ms 6220 KB Output is correct
6 Correct 75 ms 10932 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 73328 KB Output is correct
2 Correct 77 ms 10948 KB Output is correct
3 Correct 85 ms 11024 KB Output is correct
4 Correct 488 ms 15072 KB Output is correct
5 Correct 6 ms 6204 KB Output is correct
6 Correct 85 ms 10932 KB Output is correct
7 Correct 71 ms 10864 KB Output is correct
8 Correct 76 ms 11008 KB Output is correct
9 Correct 61 ms 10820 KB Output is correct
10 Correct 448 ms 18996 KB Output is correct
11 Correct 389 ms 19248 KB Output is correct
12 Correct 73 ms 10928 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 73328 KB Output is correct
2 Correct 77 ms 10948 KB Output is correct
3 Correct 85 ms 11024 KB Output is correct
4 Correct 488 ms 15072 KB Output is correct
5 Correct 6 ms 6204 KB Output is correct
6 Correct 85 ms 10932 KB Output is correct
7 Correct 71 ms 10864 KB Output is correct
8 Correct 76 ms 11008 KB Output is correct
9 Correct 61 ms 10820 KB Output is correct
10 Correct 448 ms 18996 KB Output is correct
11 Correct 389 ms 19248 KB Output is correct
12 Correct 73 ms 10928 KB Output is correct
13 Correct 141 ms 73336 KB Output is correct
14 Correct 65 ms 10984 KB Output is correct
15 Correct 74 ms 11076 KB Output is correct
16 Correct 482 ms 14948 KB Output is correct
17 Correct 6 ms 6224 KB Output is correct
18 Correct 76 ms 11100 KB Output is correct
19 Correct 61 ms 10820 KB Output is correct
20 Correct 77 ms 10996 KB Output is correct
21 Correct 59 ms 10792 KB Output is correct
22 Correct 471 ms 18984 KB Output is correct
23 Correct 382 ms 19120 KB Output is correct
24 Correct 65 ms 10812 KB Output is correct
25 Correct 1510 ms 52872 KB Output is correct
26 Correct 1433 ms 59872 KB Output is correct
27 Correct 1373 ms 52980 KB Output is correct
28 Correct 1189 ms 57604 KB Output is correct
29 Runtime error 2286 ms 524292 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 73328 KB Output is correct
2 Correct 77 ms 10948 KB Output is correct
3 Correct 85 ms 11024 KB Output is correct
4 Correct 488 ms 15072 KB Output is correct
5 Correct 6 ms 6204 KB Output is correct
6 Correct 85 ms 10932 KB Output is correct
7 Correct 71 ms 10864 KB Output is correct
8 Correct 76 ms 11008 KB Output is correct
9 Correct 61 ms 10820 KB Output is correct
10 Correct 448 ms 18996 KB Output is correct
11 Correct 389 ms 19248 KB Output is correct
12 Correct 73 ms 10928 KB Output is correct
13 Correct 141 ms 73336 KB Output is correct
14 Correct 65 ms 10984 KB Output is correct
15 Correct 74 ms 11076 KB Output is correct
16 Correct 482 ms 14948 KB Output is correct
17 Correct 6 ms 6224 KB Output is correct
18 Correct 76 ms 11100 KB Output is correct
19 Correct 61 ms 10820 KB Output is correct
20 Correct 77 ms 10996 KB Output is correct
21 Correct 59 ms 10792 KB Output is correct
22 Correct 471 ms 18984 KB Output is correct
23 Correct 382 ms 19120 KB Output is correct
24 Correct 65 ms 10812 KB Output is correct
25 Correct 1510 ms 52872 KB Output is correct
26 Correct 1433 ms 59872 KB Output is correct
27 Correct 1373 ms 52980 KB Output is correct
28 Correct 1189 ms 57604 KB Output is correct
29 Runtime error 2286 ms 524292 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 73312 KB Output is correct
2 Correct 63 ms 10956 KB Output is correct
3 Correct 86 ms 11020 KB Output is correct
4 Correct 500 ms 15040 KB Output is correct
5 Correct 6 ms 6220 KB Output is correct
6 Correct 75 ms 10932 KB Output is correct
7 Correct 141 ms 73328 KB Output is correct
8 Correct 77 ms 10948 KB Output is correct
9 Correct 85 ms 11024 KB Output is correct
10 Correct 488 ms 15072 KB Output is correct
11 Correct 6 ms 6204 KB Output is correct
12 Correct 85 ms 10932 KB Output is correct
13 Correct 71 ms 10864 KB Output is correct
14 Correct 76 ms 11008 KB Output is correct
15 Correct 61 ms 10820 KB Output is correct
16 Correct 448 ms 18996 KB Output is correct
17 Correct 389 ms 19248 KB Output is correct
18 Correct 73 ms 10928 KB Output is correct
19 Correct 4 ms 6220 KB Output is correct
20 Correct 4 ms 6220 KB Output is correct
21 Correct 4 ms 6220 KB Output is correct
22 Correct 141 ms 72932 KB Output is correct
23 Correct 63 ms 10564 KB Output is correct
24 Correct 83 ms 10684 KB Output is correct
25 Correct 477 ms 14564 KB Output is correct
26 Correct 6 ms 6220 KB Output is correct
27 Correct 73 ms 10592 KB Output is correct
28 Correct 73 ms 10548 KB Output is correct
29 Correct 67 ms 10620 KB Output is correct
30 Correct 68 ms 10472 KB Output is correct
31 Correct 468 ms 18600 KB Output is correct
32 Correct 439 ms 18748 KB Output is correct
33 Correct 67 ms 10436 KB Output is correct
34 Incorrect 4336 ms 118388 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 73312 KB Output is correct
2 Correct 63 ms 10956 KB Output is correct
3 Correct 86 ms 11020 KB Output is correct
4 Correct 500 ms 15040 KB Output is correct
5 Correct 6 ms 6220 KB Output is correct
6 Correct 75 ms 10932 KB Output is correct
7 Correct 141 ms 73328 KB Output is correct
8 Correct 77 ms 10948 KB Output is correct
9 Correct 85 ms 11024 KB Output is correct
10 Correct 488 ms 15072 KB Output is correct
11 Correct 6 ms 6204 KB Output is correct
12 Correct 85 ms 10932 KB Output is correct
13 Correct 71 ms 10864 KB Output is correct
14 Correct 76 ms 11008 KB Output is correct
15 Correct 61 ms 10820 KB Output is correct
16 Correct 448 ms 18996 KB Output is correct
17 Correct 389 ms 19248 KB Output is correct
18 Correct 73 ms 10928 KB Output is correct
19 Correct 141 ms 73336 KB Output is correct
20 Correct 65 ms 10984 KB Output is correct
21 Correct 74 ms 11076 KB Output is correct
22 Correct 482 ms 14948 KB Output is correct
23 Correct 6 ms 6224 KB Output is correct
24 Correct 76 ms 11100 KB Output is correct
25 Correct 61 ms 10820 KB Output is correct
26 Correct 77 ms 10996 KB Output is correct
27 Correct 59 ms 10792 KB Output is correct
28 Correct 471 ms 18984 KB Output is correct
29 Correct 382 ms 19120 KB Output is correct
30 Correct 65 ms 10812 KB Output is correct
31 Correct 1510 ms 52872 KB Output is correct
32 Correct 1433 ms 59872 KB Output is correct
33 Correct 1373 ms 52980 KB Output is correct
34 Correct 1189 ms 57604 KB Output is correct
35 Runtime error 2286 ms 524292 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 73312 KB Output is correct
2 Correct 63 ms 10956 KB Output is correct
3 Correct 86 ms 11020 KB Output is correct
4 Correct 500 ms 15040 KB Output is correct
5 Correct 6 ms 6220 KB Output is correct
6 Correct 75 ms 10932 KB Output is correct
7 Correct 141 ms 73328 KB Output is correct
8 Correct 77 ms 10948 KB Output is correct
9 Correct 85 ms 11024 KB Output is correct
10 Correct 488 ms 15072 KB Output is correct
11 Correct 6 ms 6204 KB Output is correct
12 Correct 85 ms 10932 KB Output is correct
13 Correct 71 ms 10864 KB Output is correct
14 Correct 76 ms 11008 KB Output is correct
15 Correct 61 ms 10820 KB Output is correct
16 Correct 448 ms 18996 KB Output is correct
17 Correct 389 ms 19248 KB Output is correct
18 Correct 73 ms 10928 KB Output is correct
19 Correct 141 ms 73336 KB Output is correct
20 Correct 65 ms 10984 KB Output is correct
21 Correct 74 ms 11076 KB Output is correct
22 Correct 482 ms 14948 KB Output is correct
23 Correct 6 ms 6224 KB Output is correct
24 Correct 76 ms 11100 KB Output is correct
25 Correct 61 ms 10820 KB Output is correct
26 Correct 77 ms 10996 KB Output is correct
27 Correct 59 ms 10792 KB Output is correct
28 Correct 471 ms 18984 KB Output is correct
29 Correct 382 ms 19120 KB Output is correct
30 Correct 65 ms 10812 KB Output is correct
31 Correct 1510 ms 52872 KB Output is correct
32 Correct 1433 ms 59872 KB Output is correct
33 Correct 1373 ms 52980 KB Output is correct
34 Correct 1189 ms 57604 KB Output is correct
35 Runtime error 2286 ms 524292 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -