Submission #869917

#	Time	Username	Problem	Language	Result	Execution time	Memory
869917		borisAngelov	Passport (JOI23_passport)	C++17	100 / 100	596 ms	103204 KiB

passport

#include <bits/stdc++.h>

using namespace std;

const int maxn = 250005;
const int inf = 1000000000;

int n, q;

int minCity[4 * maxn];
int maxCity[4 * maxn];
int distFrom1[4 * maxn];
int distFromN[4 * maxn];
int distCombined[4 * maxn];

struct Edge
{
    int to;
    int w;

    Edge(int _to, int _w)
    {
        to = _to;
        w = _w;
    }
};

struct SegmentTree
{
    int root = 0;
    int numberNodes = 0;

    struct Node
    {
        int lc;
        int rc;
        vector<Edge> edges;
    };

    Node tree[4 * maxn];

    int build(int l, int r)
    {
        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;

        int leftChild = build(l, mid);
        int rightChild = build(mid + 1, r);

        int node = ++numberNodes;

        tree[node].lc = leftChild;
        tree[node].rc = rightChild;

        tree[leftChild].edges.push_back(Edge(node, 0));
        tree[rightChild].edges.push_back(Edge(node, 0));

        return node;
    }

    void addRangeEdge(int node, int l, int r, int ql, int qr, int toNode)
    {
        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            tree[node].edges.push_back(Edge(toNode, 1));
            return;
        }

        int mid = (l + r) / 2;

        addRangeEdge(tree[node].lc, l, mid, ql, qr, toNode);
        addRangeEdge(tree[node].rc, mid + 1, r, ql, qr, toNode);
    }

    void addEdge(int x, int y, int w)
    {
        tree[x].edges.push_back(Edge(y, w));
    }

    void addRangeEdge(int to, int l, int r)
    {
        addRangeEdge(root, 1, n + 1, l, r, to);
    }

    void build()
    {
        numberNodes = n + 1;
        root = build(1, n + 1);
    }
};

SegmentTree tree;

void Dijkstra(int start, int dist[])
{
    for (int i = 1; i <= tree.numberNodes; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<int, int>> pq;

    pq.push(make_pair(0, start));
    dist[start] = 0;

    while (!pq.empty())
    {
        int node = pq.top().second;
        int curr = -pq.top().first;
        pq.pop();

        for (int i = 0; i < tree.tree[node].edges.size(); ++i)
        {
            int nextNode = tree.tree[node].edges[i].to;
            int path = curr + tree.tree[node].edges[i].w;

            if (dist[nextNode] > path)
            {
                dist[nextNode] = path;
                pq.push(make_pair(-path, nextNode));
            }
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> minCity[i] >> maxCity[i];
    }

    tree.build();

    for (int i = 1; i <= n; ++i)
    {
        tree.addRangeEdge(i, minCity[i], maxCity[i]);
    }

    Dijkstra(1, distFrom1);
    Dijkstra(n, distFromN);

    for (int i = 1; i <= n; ++i)
    {
        int weight = distFrom1[i] + distFromN[i];

        if (distFrom1[i] > 0 && distFromN[i] > 0)
        {
            --weight;
            // this is for the two issued passports from city i
        }

        tree.addEdge(n + 1, i, weight);
    }

    Dijkstra(n + 1, distCombined);

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int node;
        cin >> node;

        if (distCombined[node] > n)
        {
            cout << -1 << "\n";
        }
        else
        {
            cout << distCombined[node] << "\n";
        }
    }

    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void Dijkstra(int, int*)':
passport.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for (int i = 0; i < tree.tree[node].edges.size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46