답안 #790480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790480	2023-07-22T17:25:39 Z	Johann	Passport (JOI23_passport)	C++14	100 / 100	569 ms	47124 KB

passport

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; }
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int INF = 1 << 30;
int N, Q;
vpii R;
vi Qu;
vvi dp;
vi toL, toR, toBoth, ans; // distance

struct segtree
{
    int size;
    vvi arr;
    void init(int _size)
    {
        size = 1;
        while (size < _size)
            size *= 2;
        arr.assign(2 * size, vi());
    }
    void add(int l, int r, int i) { add(l, r, i, 1, 0, size); }
    void add(int l, int r, int i, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            arr[x].push_back(i);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        add(l, r, i, 2 * x, lx, m);
        add(l, r, i, 2 * x + 1, m, rx);
    }
    void query(int i, vi &neigh)
    {
        i += size;
        while (i > 0)
        {
            while (!arr[i].empty())
                neigh.push_back(arr[i].back()), arr[i].pop_back();
            i >>= 1;
        }
    }
};

segtree seg;

void djikstra(priority_queue<pii, vpii, greater<pii>> &q, vi &dist)
{
    seg.init(N);
    for (int i = 0; i < N; ++i)
        seg.add(R[i].first, R[i].second, i);

    vb vis(N, 0);
    vi neigh;
    while (!q.empty())
    {
        int d, v;
        tie(d, v) = q.top(), q.pop();

        if (vis[v])
            continue;

        dist[v] = d;
        vis[v] = true;
        seg.query(v, neigh);
        for (int u : neigh)
        {
            if (dist[u] <= d + 1)
                continue;
            dist[u] = d + 1;
            q.push({d + 1, u});
        }
        neigh.clear();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    R.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> R[i].first >> R[i].second, --R[i].first;
    seg.init(N);

    cin >> Q;
    Qu.resize(Q);
    for (int i = 0; i < Q; ++i)
        cin >> Qu[i], --Qu[i];

    priority_queue<pii, vpii, greater<pii>> q;
    for (int i = 0; i < N; ++i)
        if (R[i].first == 0)
            q.push({1, i});
    toL.assign(N, INF);
    djikstra(q, toL);
    assert(q.empty());

    for (int i = 0; i < N; ++i)
        if (R[i].second == N)
            q.push({1, i});
    toR.assign(N, INF);
    djikstra(q, toR);
    assert(q.empty());

    toBoth.assign(N, INF);
    for (int i = 0; i < N; ++i)
        if (toL[i] != INF && toR[i] != INF)
        {
            toBoth[i] = toL[i] + toR[i] - 1;
            q.push({toBoth[i], i});
        }
    ans.assign(N, INF);
    djikstra(q, ans);

    for (int x : Qu)
        if (ans[x] == INF)
            cout << -1 << "\n";
        else
            cout << ans[x] << "\n";

    return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	569 ms	43984 KB	Output is correct
5	Correct	255 ms	31608 KB	Output is correct
6	Correct	167 ms	30836 KB	Output is correct
7	Correct	204 ms	33496 KB	Output is correct
8	Correct	131 ms	30276 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	724 KB	Output is correct
19	Correct	3 ms	724 KB	Output is correct
20	Correct	2 ms	752 KB	Output is correct
21	Correct	2 ms	720 KB	Output is correct
22	Correct	2 ms	712 KB	Output is correct
23	Correct	3 ms	724 KB	Output is correct
24	Correct	2 ms	724 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	724 KB	Output is correct
19	Correct	3 ms	724 KB	Output is correct
20	Correct	2 ms	752 KB	Output is correct
21	Correct	2 ms	720 KB	Output is correct
22	Correct	2 ms	712 KB	Output is correct
23	Correct	3 ms	724 KB	Output is correct
24	Correct	2 ms	724 KB	Output is correct
25	Correct	1 ms	320 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	5 ms	724 KB	Output is correct
28	Correct	3 ms	724 KB	Output is correct
29	Correct	2 ms	716 KB	Output is correct
30	Correct	2 ms	724 KB	Output is correct
31	Correct	3 ms	724 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	569 ms	43984 KB	Output is correct
5	Correct	255 ms	31608 KB	Output is correct
6	Correct	167 ms	30836 KB	Output is correct
7	Correct	204 ms	33496 KB	Output is correct
8	Correct	131 ms	30276 KB	Output is correct
9	Correct	0 ms	320 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	4 ms	724 KB	Output is correct
25	Correct	3 ms	724 KB	Output is correct
26	Correct	3 ms	724 KB	Output is correct
27	Correct	3 ms	724 KB	Output is correct
28	Correct	2 ms	752 KB	Output is correct
29	Correct	2 ms	720 KB	Output is correct
30	Correct	2 ms	712 KB	Output is correct
31	Correct	3 ms	724 KB	Output is correct
32	Correct	2 ms	724 KB	Output is correct
33	Correct	1 ms	320 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	5 ms	724 KB	Output is correct
36	Correct	3 ms	724 KB	Output is correct
37	Correct	2 ms	716 KB	Output is correct
38	Correct	2 ms	724 KB	Output is correct
39	Correct	3 ms	724 KB	Output is correct
40	Correct	567 ms	46084 KB	Output is correct
41	Correct	295 ms	35100 KB	Output is correct
42	Correct	358 ms	45136 KB	Output is correct
43	Correct	372 ms	47124 KB	Output is correct
44	Correct	186 ms	34252 KB	Output is correct
45	Correct	205 ms	35916 KB	Output is correct
46	Correct	96 ms	15112 KB	Output is correct
47	Correct	281 ms	39860 KB	Output is correct
48	Correct	295 ms	37364 KB	Output is correct

답안 #790480

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 8.0 / 8.0

Subtask #5 46.0 / 46.0

Subtask #1
6.0 / 6.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
8.0 / 8.0

Subtask #5
46.0 / 46.0