Submission #896626

#	Time	Username	Problem	Language	Result	Execution time	Memory
896626		MateiKing80	Passport (JOI23_passport)	C++14	48 / 100	2096 ms	868520 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back

int l[200005], r[200005], x[200005];
int nrpas1[200005], nrpasn[200005], ans[200005];
vector<int> vec[200005];
int n, Q;
int dist[2505][2505];

void bfs1()
{
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(auto i : vec[nod])
        {
            if(i != 1 && nrpas1[i] == 0)
            {
                nrpas1[i] = nrpas1[nod] + 1;
                q.push(i);
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        if(nrpas1[i] == 0)
            nrpas1[i] = -1;
}


void bfsn()
{
    queue<int> q;
    q.push(n);
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(auto i : vec[nod])
        {
            if(i != n && nrpasn[i] == 0)
            {
                nrpasn[i] = nrpasn[nod] + 1;
                q.push(i);
            }
        }
    }
    for(int i = 1; i < n; i ++)
        if(nrpasn[i] == 0)
            nrpasn[i] = -1;
}

void calcdist(int nod)
{
    int st = l[nod], dr = r[nod], stp = nod, drp = nod, sus = 0;
    ans[nod] = nrpas1[nod] + nrpasn[nod];

    if(nrpas1[nod] == -1 || nrpasn[nod] == -1)
    {
        ans[nod] = -1;
        return;
    }
//    cout << '\n';
    while(st != stp || dr != drp)
    {
        sus ++;
//        cout << st << " " << dr << " " << stp << " " << drp << " " << sus << '\n';
        int sta = stp, dra = drp;
        stp = st, drp = dr;
        for(int i = sta - 1; i >= stp; i --)
            st = min(st, l[i]), dr = max(dr, r[i]), dist[nod][i] = sus;
        for(int i = dra + 1; i <= drp; i ++)
            dr = max(dr, r[i]), st = min(st, l[i]), dist[nod][i] = sus;
    }
    for(int i = 1; i < st; i ++)
        dist[nod][i] = 1e9;
    for(int i = dr + 1; i <= n; i ++)
        dist[nod][i] = 1e9;
    for(int i = 1; i <= n; i ++)
        if(nrpas1[i] != -1 &&  nrpasn[i] != -1)
        {
            int sus = nrpas1[i] + nrpasn[i] + dist[nod][i];
            if(nrpas1[i] != 0 && nrpasn[i] != 0)
                sus --;
            ans[nod] = min(ans[nod], sus);
        }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
        for(int j = l[i]; j <= r[i]; j ++)
            vec[j].pb(i);
    }
    cin >> Q;
    for(int i = 1; i <= Q; i ++)
        cin >> x[i];
    bfs1();
    bfsn();
    for(int i = 1; i <= Q; i ++)
        calcdist(x[i]), cout << ans[x[i]] << '\n';
//    for(int i = 1; i <= n; i ++)
//        cout << i << " " << nrpas1[i] << " " << nrpasn[i] << '\n';
//    for(int i = 1; i <= n; i ++)
//    {
//        for(int j = 1; j <= n; j ++)
//            cout << dist[i][j] << " ";
//        cout << '\n';
//    }
}

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