oj.uz

답안 #400947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400947 2021-05-08T21:45:22 Z 534351 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 149360 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 = 126;

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];
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, c};
            cc[s[j]] = i;
        }
    }
    fill(dist, dist + N, INF);
    dist[0] = 0;
    q.push({0, 0});
    while(!q.empty())
    {
        int d = q.front().fi, u = q.front().se; q.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 (cc[v] != -1)
            {
                // cerr << "check " << d + 1 << ' ' << v << endl;
                int m = ban[v].se;
                if ((d + 1) % ban[v].se == ban[v].fi) continue;
                if (cc[u] == cc[v] && (d + 1) % m == ban[u].fi && d % m == ban[v].fi) continue;
            }
            if (dist[v] > d + 1)
            {
                dist[v] = d + 1;
            }
            // cerr << u << ' ' << v << ' ' << d + 1 << endl;
            q.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

# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 9696 KB Output is correct
2 Correct 920 ms 12836 KB Output is correct
3 Correct 1268 ms 13300 KB Output is correct
4 Correct 1912 ms 13796 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1804 ms 13580 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 9704 KB Output is correct
2 Correct 920 ms 12808 KB Output is correct
3 Correct 1320 ms 13304 KB Output is correct
4 Correct 1759 ms 13880 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1394 ms 13396 KB Output is correct
7 Correct 1060 ms 13156 KB Output is correct
8 Correct 986 ms 12960 KB Output is correct
9 Correct 925 ms 12780 KB Output is correct
10 Correct 1497 ms 13476 KB Output is correct
11 Correct 1672 ms 13036 KB Output is correct
12 Correct 1351 ms 13480 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 9704 KB Output is correct
2 Correct 920 ms 12808 KB Output is correct
3 Correct 1320 ms 13304 KB Output is correct
4 Correct 1759 ms 13880 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1394 ms 13396 KB Output is correct
7 Correct 1060 ms 13156 KB Output is correct
8 Correct 986 ms 12960 KB Output is correct
9 Correct 925 ms 12780 KB Output is correct
10 Correct 1497 ms 13476 KB Output is correct
11 Correct 1672 ms 13036 KB Output is correct
12 Correct 1351 ms 13480 KB Output is correct
13 Correct 380 ms 9708 KB Output is correct
14 Correct 874 ms 12744 KB Output is correct
15 Correct 1193 ms 13248 KB Output is correct
16 Correct 1676 ms 13764 KB Output is correct
17 Correct 5 ms 6220 KB Output is correct
18 Correct 1417 ms 13464 KB Output is correct
19 Correct 1032 ms 13124 KB Output is correct
20 Correct 971 ms 12880 KB Output is correct
21 Correct 920 ms 12740 KB Output is correct
22 Correct 1600 ms 13496 KB Output is correct
23 Correct 1542 ms 13124 KB Output is correct
24 Correct 1333 ms 13508 KB Output is correct
25 Execution timed out 6100 ms 148408 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 9704 KB Output is correct
2 Correct 920 ms 12808 KB Output is correct
3 Correct 1320 ms 13304 KB Output is correct
4 Correct 1759 ms 13880 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1394 ms 13396 KB Output is correct
7 Correct 1060 ms 13156 KB Output is correct
8 Correct 986 ms 12960 KB Output is correct
9 Correct 925 ms 12780 KB Output is correct
10 Correct 1497 ms 13476 KB Output is correct
11 Correct 1672 ms 13036 KB Output is correct
12 Correct 1351 ms 13480 KB Output is correct
13 Correct 380 ms 9708 KB Output is correct
14 Correct 874 ms 12744 KB Output is correct
15 Correct 1193 ms 13248 KB Output is correct
16 Correct 1676 ms 13764 KB Output is correct
17 Correct 5 ms 6220 KB Output is correct
18 Correct 1417 ms 13464 KB Output is correct
19 Correct 1032 ms 13124 KB Output is correct
20 Correct 971 ms 12880 KB Output is correct
21 Correct 920 ms 12740 KB Output is correct
22 Correct 1600 ms 13496 KB Output is correct
23 Correct 1542 ms 13124 KB Output is correct
24 Correct 1333 ms 13508 KB Output is correct
25 Execution timed out 6100 ms 148408 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 9696 KB Output is correct
2 Correct 920 ms 12836 KB Output is correct
3 Correct 1268 ms 13300 KB Output is correct
4 Correct 1912 ms 13796 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1804 ms 13580 KB Output is correct
7 Correct 415 ms 9704 KB Output is correct
8 Correct 920 ms 12808 KB Output is correct
9 Correct 1320 ms 13304 KB Output is correct
10 Correct 1759 ms 13880 KB Output is correct
11 Correct 5 ms 6220 KB Output is correct
12 Correct 1394 ms 13396 KB Output is correct
13 Correct 1060 ms 13156 KB Output is correct
14 Correct 986 ms 12960 KB Output is correct
15 Correct 925 ms 12780 KB Output is correct
16 Correct 1497 ms 13476 KB Output is correct
17 Correct 1672 ms 13036 KB Output is correct
18 Correct 1351 ms 13480 KB Output is correct
19 Correct 4 ms 6092 KB Output is correct
20 Correct 4 ms 6220 KB Output is correct
21 Correct 4 ms 6092 KB Output is correct
22 Correct 386 ms 9580 KB Output is correct
23 Correct 880 ms 12868 KB Output is correct
24 Correct 1205 ms 13400 KB Output is correct
25 Correct 1734 ms 13704 KB Output is correct
26 Correct 5 ms 6220 KB Output is correct
27 Correct 1417 ms 13472 KB Output is correct
28 Correct 1033 ms 13252 KB Output is correct
29 Correct 974 ms 12888 KB Output is correct
30 Correct 914 ms 12892 KB Output is correct
31 Correct 1479 ms 13416 KB Output is correct
32 Correct 1542 ms 12968 KB Output is correct
33 Correct 1392 ms 13508 KB Output is correct
34 Execution timed out 6047 ms 149360 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 9696 KB Output is correct
2 Correct 920 ms 12836 KB Output is correct
3 Correct 1268 ms 13300 KB Output is correct
4 Correct 1912 ms 13796 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1804 ms 13580 KB Output is correct
7 Correct 415 ms 9704 KB Output is correct
8 Correct 920 ms 12808 KB Output is correct
9 Correct 1320 ms 13304 KB Output is correct
10 Correct 1759 ms 13880 KB Output is correct
11 Correct 5 ms 6220 KB Output is correct
12 Correct 1394 ms 13396 KB Output is correct
13 Correct 1060 ms 13156 KB Output is correct
14 Correct 986 ms 12960 KB Output is correct
15 Correct 925 ms 12780 KB Output is correct
16 Correct 1497 ms 13476 KB Output is correct
17 Correct 1672 ms 13036 KB Output is correct
18 Correct 1351 ms 13480 KB Output is correct
19 Correct 380 ms 9708 KB Output is correct
20 Correct 874 ms 12744 KB Output is correct
21 Correct 1193 ms 13248 KB Output is correct
22 Correct 1676 ms 13764 KB Output is correct
23 Correct 5 ms 6220 KB Output is correct
24 Correct 1417 ms 13464 KB Output is correct
25 Correct 1032 ms 13124 KB Output is correct
26 Correct 971 ms 12880 KB Output is correct
27 Correct 920 ms 12740 KB Output is correct
28 Correct 1600 ms 13496 KB Output is correct
29 Correct 1542 ms 13124 KB Output is correct
30 Correct 1333 ms 13508 KB Output is correct
31 Execution timed out 6100 ms 148408 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 9696 KB Output is correct
2 Correct 920 ms 12836 KB Output is correct
3 Correct 1268 ms 13300 KB Output is correct
4 Correct 1912 ms 13796 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 1804 ms 13580 KB Output is correct
7 Correct 415 ms 9704 KB Output is correct
8 Correct 920 ms 12808 KB Output is correct
9 Correct 1320 ms 13304 KB Output is correct
10 Correct 1759 ms 13880 KB Output is correct
11 Correct 5 ms 6220 KB Output is correct
12 Correct 1394 ms 13396 KB Output is correct
13 Correct 1060 ms 13156 KB Output is correct
14 Correct 986 ms 12960 KB Output is correct
15 Correct 925 ms 12780 KB Output is correct
16 Correct 1497 ms 13476 KB Output is correct
17 Correct 1672 ms 13036 KB Output is correct
18 Correct 1351 ms 13480 KB Output is correct
19 Correct 380 ms 9708 KB Output is correct
20 Correct 874 ms 12744 KB Output is correct
21 Correct 1193 ms 13248 KB Output is correct
22 Correct 1676 ms 13764 KB Output is correct
23 Correct 5 ms 6220 KB Output is correct
24 Correct 1417 ms 13464 KB Output is correct
25 Correct 1032 ms 13124 KB Output is correct
26 Correct 971 ms 12880 KB Output is correct
27 Correct 920 ms 12740 KB Output is correct
28 Correct 1600 ms 13496 KB Output is correct
29 Correct 1542 ms 13124 KB Output is correct
30 Correct 1333 ms 13508 KB Output is correct
31 Execution timed out 6100 ms 148408 KB Time limit exceeded
32 Halted 0 ms 0 KB -