Submission #768730

#	Time	Username	Problem	Language	Result	Execution time	Memory
768730		danikoynov	Passport (JOI23_passport)	C++14	100 / 100	697 ms	607948 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 = 2e5 + 10;


vector < pair < int, int > > adj[maxn * 2];
int dist[maxn * 2], lf[maxn * 2], rf[maxn * 2];
int fict, root, toi;


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;
}
void graph(int _n)
{
    toi = _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, toi, l, r, v);
}
void add_edge(int v, int u, int w)
{
    adj[v].push_back({u, w});
    ///adj[u].push_back({v, w});
}
int used[4 * maxn];
struct edge
{
    int v, len;
    edge(int _v = 0, int _len = 0)
    {
        v = _v;
        len = _len;
    }
    bool operator < (const edge &e) const
    {
        return len > e.len;
    }
};
 queue < int > qs[4 * maxn];
void bfs(int st, bool tf = false)
{
    for (int i = 1; i <= fict; i ++)
    {
        dist[i] = 1e9;
        used[i] = 0;
    }


    qs[0].push(st);
    dist[st] = 0;

    for (int i = 0; i < 4 * maxn; i ++)
    while(!qs[i].empty())
    {
        int cur = qs[i].front();
        qs[i].pop();
        //cout << cur << " " << used[cur] << endl;
        if (used[cur])
            continue;
        used[cur] = 1;
        //if (tf)
          //  cout << "here " << v << " " << dist[v] << endl;
        for (pair < int, int > nb : adj[cur])
        {

            if (dist[nb.first] > dist[cur] + nb.second)
            {
                dist[nb.first] = dist[cur] + nb.second;
                qs[dist[cur] + nb.second].push(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(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        add_range_edge(l[i], r[i], i);
        ///for (int j = l[i]; j <= r[i]; j ++)
        ///add_edge(j, i, 1);
        ///cout << j << " " << i << " " << 1 << endl;
    }

    bfs(1);
    for (int i = 1; i <= n; i ++)
        a[i] = dist[i];
    bfs(n);
    for (int i = 1; i <= n; i ++)
        b[i] = 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 --;
        add_edge(n + 1, i, edge);
        ///cout << n + 1 << " " << i << " " << a[i] << " " << b[i] << endl;
    }

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



}

int main()
{
    speed();
    ///freopen("text.txt", "r", stdin);
    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: 46 / 46