oj.uz

Submission #864142

# Submission time Handle Problem Language Result Execution time Memory
864142 2023-10-22T07:23:47 Z danikoynov Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 48328 KB 
#include<bits/stdc++.h>
#define debug true
#ifdef DEVAL 
    #define debug false
#endif

using namespace std;

const int maxn = 1e5 + 10;

struct interval
{
    int s, e;
}seg[maxn];

int n, q;   
pair < int, int > task[maxn];
void read()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> seg[i].s >> seg[i].e;
    }
    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].first >> task[i].second;
    }
}


vector < int > adj[maxn];

int used[maxn], dist[5010][5010];

void bfs(int start)
{
    for (int i = 1; i <= n; i ++)
        used[i] = -1;

    used[start] = 0;
    queue < int > q;
    q.push(start);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        for (int u : adj[v])
        {
            if (used[u] == - 1)
            {
                used[u] = used[v] + 1;
                q.push(u);
            }
        }
    }
}

void build_graph()
{
    for (int i = 1; i <= n; i ++)
       for (int j = 1; j <= n; j ++)
        {
            if (seg[j].s <= seg[i].e && seg[i].e <= seg[j].e)
                adj[i].push_back(j);
        }
}

void answer_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        if (dist[task[i].first][task[i].second] == -1)
            cout << "impossible" << endl;
        else
            cout << dist[task[i].first][task[i].second] << endl;

    }
}

void precalc()
{
    for (int v = 1; v <= n; v ++)
    {
        bfs(v);
        for (int i = 1; i <= n; i ++)
            dist[v][i] = used[i];
    }
}
void solve()
{
    read();
    build_graph();
    precalc();
    answer_queries();    
}

int main()
{
    solve();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Execution timed out 1531 ms 6856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 13 ms 25400 KB Output is correct
4 Correct 11 ms 25432 KB Output is correct
5 Correct 13 ms 25312 KB Output is correct
6 Correct 43 ms 26196 KB Output is correct
7 Correct 109 ms 27004 KB Output is correct
8 Correct 123 ms 28024 KB Output is correct
9 Correct 665 ms 29620 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 13 ms 25400 KB Output is correct
4 Correct 11 ms 25432 KB Output is correct
5 Correct 13 ms 25312 KB Output is correct
6 Correct 43 ms 26196 KB Output is correct
7 Correct 109 ms 27004 KB Output is correct
8 Correct 123 ms 28024 KB Output is correct
9 Correct 665 ms 29620 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 13 ms 25432 KB Output is correct
13 Correct 11 ms 25436 KB Output is correct
14 Correct 14 ms 25424 KB Output is correct
15 Correct 39 ms 26188 KB Output is correct
16 Correct 106 ms 26988 KB Output is correct
17 Correct 129 ms 28048 KB Output is correct
18 Correct 636 ms 29360 KB Output is correct
19 Execution timed out 1554 ms 48328 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 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 13 ms 25400 KB Output is correct
4 Correct 11 ms 25432 KB Output is correct
5 Correct 13 ms 25312 KB Output is correct
6 Correct 43 ms 26196 KB Output is correct
7 Correct 109 ms 27004 KB Output is correct
8 Correct 123 ms 28024 KB Output is correct
9 Correct 665 ms 29620 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 14 ms 25436 KB Output is correct
13 Correct 11 ms 25320 KB Output is correct
14 Correct 15 ms 25436 KB Output is correct
15 Correct 39 ms 26188 KB Output is correct
16 Correct 105 ms 26964 KB Output is correct
17 Correct 124 ms 28044 KB Output is correct
18 Correct 638 ms 29780 KB Output is correct
19 Execution timed out 1566 ms 5716 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1560 ms 6432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Execution timed out 1531 ms 6856 KB Time limit exceeded
3 Halted 0 ms 0 KB -