oj.uz

답안 #636967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636967 2022-08-30T20:25:07 Z danikoynov Railway Trip 2 (JOI22_ho_t4) C++14
8 / 100
 2000 ms 3160 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 solve_query(int s, int t)
{
    for (int i = 1; i <= n; i ++)
    {
        used[i] = 0;
        par[i] = lf[i] = rf[i] = i;
    }
    queue < int > q;
    used[s] = 1;
    lf[s] = s - 1;
    rf[s] = s + 1;
    q.push(s);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << "cur: " << cur << endl;
        for (int i = 1; i <= m; i ++)
        {
            if (on_train(cur, i))
            {
                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);
                        q.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);
                        q.push(j);
                        j --;
                    }

                }
            }
        }
    }

    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 60 ms 340 KB Output is correct
2 Correct 73 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 56 ms 340 KB Output is correct
5 Correct 77 ms 340 KB Output is correct
6 Correct 166 ms 340 KB Output is correct
7 Correct 121 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 110 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 66 ms 340 KB Output is correct
12 Correct 12 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 340 KB Output is correct
2 Correct 73 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 56 ms 340 KB Output is correct
5 Correct 77 ms 340 KB Output is correct
6 Correct 166 ms 340 KB Output is correct
7 Correct 121 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 110 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 66 ms 340 KB Output is correct
12 Correct 12 ms 332 KB Output is correct
13 Execution timed out 2090 ms 464 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 340 KB Output is correct
2 Correct 73 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 56 ms 340 KB Output is correct
5 Correct 77 ms 340 KB Output is correct
6 Correct 166 ms 340 KB Output is correct
7 Correct 121 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 110 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 66 ms 340 KB Output is correct
12 Correct 12 ms 332 KB Output is correct
13 Execution timed out 2090 ms 464 KB Time limit exceeded
14 Halted 0 ms 0 KB -