Submission #768705

#	Time	Username	Problem	Language	Result	Execution time	Memory
768705		danikoynov	Passport (JOI23_passport)	C++14	54 / 100	2097 ms	89620 KiB

passport

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2.5e5 + 10;

struct graph
{
    vector < pair < int, int > > adj[maxn * 4];
    int dist[maxn * 4], lf[maxn * 4], rf[maxn * 4];
    int fict, root, n;
    graph() {};

    int build(int left, int right)
    {
        ///cout << left << " :: " << right << " " << fict << endl;
        if (left == right)
            return left;
        int mid = (left + right) / 2;
        int left_child = build(left, mid);
        int right_child = build(mid + 1, right);
        int ver = ++ fict;
        adj[left_child].push_back({ver, 0});
        adj[right_child].push_back({ver, 0});
        //cout << left_child << " " << ver << " " << 0 << endl;
        //cout << right_child << " " << ver << " " << 0 << endl;
        lf[ver] = left_child;
        rf[ver] = right_child;
        return ver;
    }
    graph(int _n)
    {
        n = _n;
        fict = n;
        root = build(1, n);

    }

    void range_update(int node, int l, int r, int ql, int qr, int v)
    {
        if (l > qr || r < ql)
        return;

        if (l >= ql && r <= qr)
        {
            adj[node].push_back({v, 1});
            ///cout << "make edge " << node << " " << l << " " << r << " " << v << endl;
            ///cout << node << " " << v << " " << 1 << endl;
            return;
        }

        int m = (l + r) / 2;
        range_update(lf[node], l, m, ql, qr, v);
        range_update(rf[node], m + 1, r, ql, qr, v);
    }
    void add_range_edge(int l, int r, int v)
    {
        range_update(root, 1, n, l, r, v);
    }
    void add_edge(int v, int u, int w)
    {
        adj[v].push_back({u, w});
        ///adj[u].push_back({v, w});
    }

    void bfs(int st)
    {
        for (int i = 1; i <= fict; i ++)
        {
            dist[i] = 1e9;
        }

        deque < int > q;
        dist[st] = 0;
        q.push_back(st);
        while(!q.empty())
        {
            int v = q.front();
            q.pop_front();
            ///cout << "here " << v << " " << dist[v] << endl;
            for (pair < int, int > nb : adj[v])
            {
                if (dist[nb.first] > dist[v] + nb.second)
                {
                    dist[nb.first] = dist[v] + nb.second;
                    if (nb.second == 0)
                        q.push_front(nb.first);
                    else
                        q.push_back(nb.first);
                }
            }
        }
    }
};

int n, q, l[maxn], r[maxn];
int a[maxn], b[maxn];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }

    graph st(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        st.add_range_edge(l[i], r[i], i);
        ///for (int j = l[i]; j <= r[i]; j ++)
            ///st.add_edge(j, i, 1);
            ///cout << j << " " << i << " " << 1 << endl;
    }

    st.bfs(1);
    for (int i = 1; i <= n; i ++)
        a[i] = st.dist[i];
    st.bfs(n);
    for (int i = 1; i <= n; i ++)
        b[i] = st.dist[i];

    /**for (int i = 1; i <= n; i ++)
        cout << b[i] << " ";
    cout << endl;
    return;*/
    ///cout << "------------" << endl;
    for (int i = 1; i <= n; i ++)
    {
        int edge = a[i] + b[i];
        if (a[i] > 0 && b[i] > 0)
            edge --;
        st.add_edge(n + 1, i, edge);
        ///cout << n + 1 << " " << i << " " << a[i] << " " << b[i] << endl;
    }


    st.bfs(n + 1);
    /**for (int i = 1; i <= n; i ++)
        cout << st.dist[i] << " ";
    cout << endl;*/
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int x;
        cin >> x;
        int ans = st.dist[x];
        if (ans > n)
            cout << -1 << endl;
        else
        cout << ans << endl;
    }



}

int main()
{
    speed();
    solve();
    return 0;
}
/**
9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

*/

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