oj.uz

Submission #1109035

# Submission time Handle Problem Language Result Execution time Memory
1109035 2024-11-05T20:48:44 Z n3rm1n Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 30844 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 5e3 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, q, s[MAXN], e[MAXN];
void read_events()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
        cin >> s[i] >> e[i];
}
vector < int > g[MAXN];

void make_edges()
{
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            if(i == j)continue;
            if(s[j] <= e[i] && e[i] <= e[j])
                g[i].push_back(j);
        }
    }
}
vector < pair < int, int > > que[MAXN];

int start, dist[MAXN], used[MAXN];
void bfs()
{
    for (int i = 1; i <= n; ++ i)
    {
        dist[i] = 1e9;
        used[i] = 0;
    }
    queue < int > q;
    q.push(start);
    used[start] = 1;
    dist[start] = 0;
    while(!q.empty())
    {
        int beg = q.front();
        q.pop();
        for (auto nb: g[beg])
        {
            if(used[nb])continue;
            dist[nb] = dist[beg] + 1;
            used[nb] = 1;
            q.push(nb);
        }
    }
}

int main()
{
    speed();

    read_events();
    make_edges();

    for (int i = 1; i <= q; ++ i)
    {
        int from, to;
        cin >> from >> to;
        start = from;
        bfs();

        if(dist[to] == 1e9)cout << "impossible" << endl;
        else cout << dist[to] << endl;
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Runtime error 3 ms 1076 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 4 ms 592 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 8 ms 1528 KB Output is correct
7 Correct 16 ms 2384 KB Output is correct
8 Correct 17 ms 3324 KB Output is correct
9 Correct 93 ms 4688 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 4 ms 592 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 8 ms 1528 KB Output is correct
7 Correct 16 ms 2384 KB Output is correct
8 Correct 17 ms 3324 KB Output is correct
9 Correct 93 ms 4688 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 4 ms 592 KB Output is correct
15 Correct 7 ms 1360 KB Output is correct
16 Correct 17 ms 2128 KB Output is correct
17 Correct 17 ms 3408 KB Output is correct
18 Correct 86 ms 4688 KB Output is correct
19 Execution timed out 1584 ms 30844 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 4 ms 592 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 8 ms 1528 KB Output is correct
7 Correct 16 ms 2384 KB Output is correct
8 Correct 17 ms 3324 KB Output is correct
9 Correct 93 ms 4688 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 3 ms 740 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 16 ms 2128 KB Output is correct
17 Correct 16 ms 3440 KB Output is correct
18 Correct 106 ms 4688 KB Output is correct
19 Runtime error 3 ms 1360 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Runtime error 3 ms 1076 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -