Submission #768700

#	Time	Username	Problem	Language	Result	Execution time	Memory
768700		danikoynov	Passport (JOI23_passport)	C++14	48 / 100	2088 ms	667572 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 = 3e5 + 10;

struct graph
{
    vector < vector < pair < int, int > > > adj;
    int dist[maxn], n;

    graph() {};

    graph(int _n)
    {
        n = _n;
        adj.resize(n + 1);
    }

    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 <= n; 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 ++)
    {
        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 << a[i] << " ";
        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] - 1 << endl;
    }

    st.bfs(n + 1);

    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: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46