Submission #1109784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109784	2024-11-07T15:14:49 Z	_callmelucian	Passport (JOI23_passport)	C++14	100 / 100	603 ms	92704 KB

passport

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5, NODE = 9e5 + 5;
int dist[3][mn], distanc[NODE], leaf[NODE], node[NODE], n, maxNode;
vector<pii> adj[NODE];
bool vis[NODE];

void buildTree (int k, int l, int r) {
    maxNode = max(maxNode, k);
    if (l == r)
        return leaf[l] = k, void();
    int mid = (l + r) >> 1;
    adj[2 * k].emplace_back(k, 0), buildTree(2 * k, l, mid);
    adj[2 * k + 1].emplace_back(k, 0), buildTree(2 * k + 1, mid + 1, r);
}

void buildEdge (int idx, int a, int b, int k, int l, int r) {
    if (b < l || r < a) return;
    if (a <= l && r <= b)
        return adj[k].emplace_back(node[idx], 1), void();
    int mid = (l + r) >> 1;
    buildEdge(idx, a, b, 2 * k, l, mid);
    buildEdge(idx, a, b, 2 * k + 1, mid + 1, r);
}

void bfs (int save, int source) {
    for (int i = 1; i <= maxNode; i++)
        distanc[i] = INT_MAX, vis[i] = 0;
    distanc[leaf[source]] = 0;
    deque<int> dq; dq.push_back(leaf[source]);

    while (dq.size()) {
        int u = dq.front(); dq.pop_front();
        if (vis[u]) continue;
        vis[u] = 1;

        for (pii item : adj[u]) {
            int v, w; tie(v, w) = item;
            if (distanc[u] + w < distanc[v]) {
                distanc[v] = distanc[u] + w;
                if (w) dq.push_back(v);
                else dq.push_front(v);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        dist[save][i] = distanc[node[i]];
}

void dijkstra (int save, vector<pii> &sources) {
    for (int i = 1; i <= maxNode; i++) distanc[i] = INT_MAX, vis[i] = 0;
    priority_queue<pii> pq;

    for (pii item : sources) {
        int u, dst; tie(u, dst) = item;
        pq.emplace(-dst, node[u]);
        distanc[node[u]] = dst;
    }

    while (pq.size()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;

        for (pii item : adj[u]) {
            int v, w; tie(v, w) = item;
            if (distanc[u] + w < distanc[v]) {
                distanc[v] = distanc[u] + w;
                pq.emplace(-distanc[v], v);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        dist[save][i] = distanc[node[i]];
}

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

    cin >> n;

    // build segment tree graph
    buildTree(1, 1, n);
    for (int i = 1; i <= n; i++) {
        node[i] = maxNode + i;
        adj[node[i]].emplace_back(leaf[i], 0);
    }
    maxNode += n;
    for (int i = 1; i <= n; i++) {
        int L, R; cin >> L >> R;
        buildEdge(i, L, R, 1, 1, n);
    }

    // phase 1: bfs from 1 and n
    bfs(0, 1), bfs(1, n);

    // phase 2: merge paths and continue with dijkstra
    vector<pii> sources;
    for (int i = 1; i <= n; i++)
        if (max(dist[0][i], dist[1][i]) != INT_MAX)
            sources.emplace_back(i, dist[0][i] + dist[1][i] - 1);
    dijkstra(2, sources);

    // answer queries
    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (dist[2][x] == INT_MAX ? -1 : dist[2][x]) << "\n";
    }

    return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	29008 KB	Output is correct
2	Correct	6 ms	29372 KB	Output is correct
3	Correct	5 ms	29008 KB	Output is correct
4	Correct	568 ms	88576 KB	Output is correct
5	Correct	278 ms	67772 KB	Output is correct
6	Correct	180 ms	62880 KB	Output is correct
7	Correct	131 ms	60736 KB	Output is correct
8	Correct	91 ms	59124 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	29008 KB	Output is correct
2	Correct	5 ms	29148 KB	Output is correct
3	Correct	6 ms	29008 KB	Output is correct
4	Correct	5 ms	29176 KB	Output is correct
5	Correct	6 ms	29020 KB	Output is correct
6	Correct	6 ms	29008 KB	Output is correct
7	Correct	5 ms	29176 KB	Output is correct
8	Correct	5 ms	29008 KB	Output is correct
9	Correct	6 ms	29008 KB	Output is correct
10	Correct	7 ms	29008 KB	Output is correct
11	Correct	5 ms	29008 KB	Output is correct
12	Correct	6 ms	29184 KB	Output is correct
13	Correct	5 ms	29264 KB	Output is correct
14	Correct	5 ms	29264 KB	Output is correct
15	Correct	5 ms	29256 KB	Output is correct

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	29008 KB	Output is correct
2	Correct	5 ms	29148 KB	Output is correct
3	Correct	6 ms	29008 KB	Output is correct
4	Correct	5 ms	29176 KB	Output is correct
5	Correct	6 ms	29020 KB	Output is correct
6	Correct	6 ms	29008 KB	Output is correct
7	Correct	5 ms	29176 KB	Output is correct
8	Correct	5 ms	29008 KB	Output is correct
9	Correct	6 ms	29008 KB	Output is correct
10	Correct	7 ms	29008 KB	Output is correct
11	Correct	5 ms	29008 KB	Output is correct
12	Correct	6 ms	29184 KB	Output is correct
13	Correct	5 ms	29264 KB	Output is correct
14	Correct	5 ms	29264 KB	Output is correct
15	Correct	5 ms	29256 KB	Output is correct
16	Correct	9 ms	29520 KB	Output is correct
17	Correct	10 ms	29520 KB	Output is correct
18	Correct	9 ms	29888 KB	Output is correct
19	Correct	8 ms	29776 KB	Output is correct
20	Correct	7 ms	29520 KB	Output is correct
21	Correct	7 ms	29520 KB	Output is correct
22	Correct	6 ms	29520 KB	Output is correct
23	Correct	8 ms	29520 KB	Output is correct
24	Correct	7 ms	29520 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	29008 KB	Output is correct
2	Correct	5 ms	29148 KB	Output is correct
3	Correct	6 ms	29008 KB	Output is correct
4	Correct	5 ms	29176 KB	Output is correct
5	Correct	6 ms	29020 KB	Output is correct
6	Correct	6 ms	29008 KB	Output is correct
7	Correct	5 ms	29176 KB	Output is correct
8	Correct	5 ms	29008 KB	Output is correct
9	Correct	6 ms	29008 KB	Output is correct
10	Correct	7 ms	29008 KB	Output is correct
11	Correct	5 ms	29008 KB	Output is correct
12	Correct	6 ms	29184 KB	Output is correct
13	Correct	5 ms	29264 KB	Output is correct
14	Correct	5 ms	29264 KB	Output is correct
15	Correct	5 ms	29256 KB	Output is correct
16	Correct	9 ms	29520 KB	Output is correct
17	Correct	10 ms	29520 KB	Output is correct
18	Correct	9 ms	29888 KB	Output is correct
19	Correct	8 ms	29776 KB	Output is correct
20	Correct	7 ms	29520 KB	Output is correct
21	Correct	7 ms	29520 KB	Output is correct
22	Correct	6 ms	29520 KB	Output is correct
23	Correct	8 ms	29520 KB	Output is correct
24	Correct	7 ms	29520 KB	Output is correct
25	Correct	6 ms	29176 KB	Output is correct
26	Correct	5 ms	29008 KB	Output is correct
27	Correct	9 ms	29944 KB	Output is correct
28	Correct	9 ms	29520 KB	Output is correct
29	Correct	8 ms	29520 KB	Output is correct
30	Correct	7 ms	29520 KB	Output is correct
31	Correct	7 ms	29520 KB	Output is correct

Subtask #5
46.0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	29008 KB	Output is correct
2	Correct	6 ms	29372 KB	Output is correct
3	Correct	5 ms	29008 KB	Output is correct
4	Correct	568 ms	88576 KB	Output is correct
5	Correct	278 ms	67772 KB	Output is correct
6	Correct	180 ms	62880 KB	Output is correct
7	Correct	131 ms	60736 KB	Output is correct
8	Correct	91 ms	59124 KB	Output is correct
9	Correct	5 ms	29008 KB	Output is correct
10	Correct	5 ms	29148 KB	Output is correct
11	Correct	6 ms	29008 KB	Output is correct
12	Correct	5 ms	29176 KB	Output is correct
13	Correct	6 ms	29020 KB	Output is correct
14	Correct	6 ms	29008 KB	Output is correct
15	Correct	5 ms	29176 KB	Output is correct
16	Correct	5 ms	29008 KB	Output is correct
17	Correct	6 ms	29008 KB	Output is correct
18	Correct	7 ms	29008 KB	Output is correct
19	Correct	5 ms	29008 KB	Output is correct
20	Correct	6 ms	29184 KB	Output is correct
21	Correct	5 ms	29264 KB	Output is correct
22	Correct	5 ms	29264 KB	Output is correct
23	Correct	5 ms	29256 KB	Output is correct
24	Correct	9 ms	29520 KB	Output is correct
25	Correct	10 ms	29520 KB	Output is correct
26	Correct	9 ms	29888 KB	Output is correct
27	Correct	8 ms	29776 KB	Output is correct
28	Correct	7 ms	29520 KB	Output is correct
29	Correct	7 ms	29520 KB	Output is correct
30	Correct	6 ms	29520 KB	Output is correct
31	Correct	8 ms	29520 KB	Output is correct
32	Correct	7 ms	29520 KB	Output is correct
33	Correct	6 ms	29176 KB	Output is correct
34	Correct	5 ms	29008 KB	Output is correct
35	Correct	9 ms	29944 KB	Output is correct
36	Correct	9 ms	29520 KB	Output is correct
37	Correct	8 ms	29520 KB	Output is correct
38	Correct	7 ms	29520 KB	Output is correct
39	Correct	7 ms	29520 KB	Output is correct
40	Correct	603 ms	92476 KB	Output is correct
41	Correct	342 ms	68292 KB	Output is correct
42	Correct	408 ms	92448 KB	Output is correct
43	Correct	361 ms	92704 KB	Output is correct
44	Correct	205 ms	63160 KB	Output is correct
45	Correct	244 ms	67620 KB	Output is correct
46	Correct	97 ms	42804 KB	Output is correct
47	Correct	279 ms	72376 KB	Output is correct
48	Correct	236 ms	75952 KB	Output is correct

Submission #1109784

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