oj.uz

답안 #636966

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 340 KB Output is correct
2 Correct 92 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 339 ms 332 KB Output is correct
5 Correct 90 ms 312 KB Output is correct
6 Execution timed out 2075 ms 212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 340 KB Output is correct
2 Correct 92 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 339 ms 332 KB Output is correct
5 Correct 90 ms 312 KB Output is correct
6 Execution timed out 2075 ms 212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 340 KB Output is correct
2 Correct 92 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 339 ms 332 KB Output is correct
5 Correct 90 ms 312 KB Output is correct
6 Execution timed out 2075 ms 212 KB Time limit exceeded
7 Halted 0 ms 0 KB -