Submission #636968

#	Time	Username	Problem	Language	Result	Execution time	Memory
636968		danikoynov	Railway Trip 2 (JOI22_ho_t4)	C++14	8 / 100	2073 ms	4180 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#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 = 1e5 + 10;

struct road
{
    int a, b;
} r[maxn];

struct interval
{
    int l, r, idx;

    interval(int _l = 0, int _r = 0, int _idx = 0)
    {
        l = _l;
        r = _r;
        idx = _idx;
    }

    bool operator < (const interval &it) const
    {
        return make_pair(l, r) < make_pair(it.l, it.r);
    }
};

int n, k, m, q;

bool on_train(int pos, int idx)
{
    if (r[idx].a < r[idx].b)
    {
        return (pos >= r[idx].a && pos <= r[idx].a + k - 1);
    }
    else
    {
        return (pos >= r[idx].a - k + 1 && pos <= r[idx].a);
    }
}

int used[maxn];
int par[maxn], lf[maxn], rf[maxn];

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}
void unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    par[u] = v;
    lf[v] = min(lf[v], lf[u]);
    rf[v] = max(rf[v], rf[u]);
}

int nxt[maxn], bef[maxn], us[maxn];
int solve_query(int s, int t)
{
    for (int i = 1; i <= n; i ++)
    {
        used[i] = 0;
        par[i] = lf[i] = rf[i] = i;
    }
    for (int i = 1; i <= m; i ++)
    {
        us[i] = 0;
        nxt[i] = i + 1;
        bef[i] = i - 1;
    }
    queue < int > pq;
    used[s] = 1;
    lf[s] = s - 1;
    rf[s] = s + 1;
    pq.push(s);
    while(!pq.empty())
    {
        int cur = pq.front();
        pq.pop();
        ///cout << "cur: " << cur << endl;
        int i = 1;
        while(i <= m)
        {
            if (us[i])
            {
                i = nxt[i];
                continue;
            }

            if (on_train(cur, i))
            {
                nxt[bef[i]] = nxt[i];
                bef[nxt[i]] = bef[i];
                us[i] = 1;
                if (r[i].a < r[i].b)
                {
                    int j = cur;
                    while(j <= r[i].b)
                    {
                        if (used[j])
                        {
                            j = rf[find_leader(j)];
                            continue;
                        }
                        used[j] = used[cur] + 1;
                        lf[j] = j - 1;
                        rf[j] = j + 1;
                        if (used[j - 1])
                            unite(j, j - 1);
                        if (used[j + 1])
                            unite(j, j + 1);
                        pq.push(j);
                        j ++;
                    }
                }
                else
                {
                    int j = cur;
                    while(j >= r[i].b)
                    {
                        if (used[j])
                        {
                            j = lf[find_leader(j)];
                            continue;
                        }

                        used[j] = used[cur] + 1;
                        lf[j] = j - 1;
                        rf[j] = j + 1;
                        if (used[j - 1])
                            unite(j, j - 1);
                        if (used[j + 1])
                            unite(j, j + 1);
                        pq.push(j);
                        j --;
                    }

                }
            }
            i = nxt[i];
        }
    }

    return used[t] - 1;

}
void solve()
{
    cin >> n >> k;
    cin >> m;
    for (int i = 1; i <= m; i ++)
        cin >> r[i].a >> r[i].b;

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int s, t;
        cin >> s >> t;
        int ans = solve_query(s, t);
        cout << ans << endl;
    }
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
5 2
2
5 1
3 5
1
3 2
*/

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13