oj.uz

Submission #864143

# Submission time Handle Problem Language Result Execution time Memory
864143 2023-10-22T07:26:21 Z danikoynov Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 48212 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 speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void solve()
{

    read();
    build_graph();
    precalc();
    answer_queries();    
}

int main()
{
    speed();
    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 1587 ms 6432 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 25436 KB Output is correct
4 Correct 10 ms 25320 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 39 ms 26200 KB Output is correct
7 Correct 106 ms 26988 KB Output is correct
8 Correct 126 ms 27988 KB Output is correct
9 Correct 638 ms 29424 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 25436 KB Output is correct
4 Correct 10 ms 25320 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 39 ms 26200 KB Output is correct
7 Correct 106 ms 26988 KB Output is correct
8 Correct 126 ms 27988 KB Output is correct
9 Correct 638 ms 29424 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 13 ms 25324 KB Output is correct
13 Correct 10 ms 25436 KB Output is correct
14 Correct 14 ms 25436 KB Output is correct
15 Correct 39 ms 26212 KB Output is correct
16 Correct 109 ms 27000 KB Output is correct
17 Correct 124 ms 28044 KB Output is correct
18 Correct 642 ms 29388 KB Output is correct
19 Execution timed out 1567 ms 48212 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 25436 KB Output is correct
4 Correct 10 ms 25320 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 39 ms 26200 KB Output is correct
7 Correct 106 ms 26988 KB Output is correct
8 Correct 126 ms 27988 KB Output is correct
9 Correct 638 ms 29424 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 13 ms 25436 KB Output is correct
13 Correct 10 ms 25440 KB Output is correct
14 Correct 13 ms 25320 KB Output is correct
15 Correct 39 ms 26196 KB Output is correct
16 Correct 106 ms 26912 KB Output is correct
17 Correct 126 ms 27984 KB Output is correct
18 Correct 645 ms 29652 KB Output is correct
19 Execution timed out 1525 ms 5720 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 1522 ms 6364 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 1587 ms 6432 KB Time limit exceeded
3 Halted 0 ms 0 KB -