oj.uz

답안 #636968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636968 2022-08-30T20:41:39 Z danikoynov Railway Trip 2 (JOI22_ho_t4) C++14
8 / 100
 2000 ms 4180 KB 
/**
 ____ ____ ____ ____ ____ ____
||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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 340 KB Output is correct
2 Correct 43 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 27 ms 340 KB Output is correct
5 Correct 57 ms 340 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 15 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 15 ms 364 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 52 ms 340 KB Output is correct
12 Correct 6 ms 340 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 340 KB Output is correct
2 Correct 43 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 27 ms 340 KB Output is correct
5 Correct 57 ms 340 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 15 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 15 ms 364 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 52 ms 340 KB Output is correct
12 Correct 6 ms 340 KB Output is correct
13 Execution timed out 2073 ms 412 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2069 ms 3952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2037 ms 4180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 2004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 340 KB Output is correct
2 Correct 43 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 27 ms 340 KB Output is correct
5 Correct 57 ms 340 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 15 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 15 ms 364 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 52 ms 340 KB Output is correct
12 Correct 6 ms 340 KB Output is correct
13 Execution timed out 2073 ms 412 KB Time limit exceeded
14 Halted 0 ms 0 KB -