oj.uz

Submission #1048020

# Submission time Handle Problem Language Result Execution time Memory
1048020 2024-08-07T20:18:29 Z sofijavelkovska Event Hopping (BOI22_events) C++17
10 / 100
 201 ms 17180 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5;

int n;
int l[MAXN], r[MAXN];
vector<int> adj[MAXN];
int in[MAXN], out[MAXN], level[MAXN];
int timer=0;

bool compare(int x, int y)
{
    if (r[x]==r[y])
        return l[x]<l[y];

    return r[x]<r[y];
}

void traverse(int x, int k)
{
    level[x]=k;
    timer=timer+1;
    in[x]=timer;
    for (auto y : adj[x])
        traverse(y, k+1);
    out[x]=timer;

    return;
}

bool ancestor(int x, int y)
{
    return in[x]>=in[y] && out[x]<=out[y];
}

int main()
{
    int q;
    cin >> n >> q;
    for (int i=0; i<n; i++)
        cin >> l[i] >> r[i];
    int sorted[n];
    for (int i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, compare);
    int parent[n];
    for (int i=0; i<n; i++)
        parent[i]=-1;
    int leftmost=sorted[n-1];
    for (int i=n-1; i>=0; i--)
    {
        int x=sorted[i];
        if (l[leftmost]<=r[x] && leftmost!=x)
        {
            parent[x]=leftmost;
            adj[leftmost].push_back(x);
        }
        if (l[x]<l[leftmost])
            leftmost=x;
    }
    for (int i=0; i<n; i++)
        if (parent[i]==-1)
            traverse(i, 0);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        x=x-1;
        y=y-1;
        if (x==y)
        {
            cout << 0 << '\n';
            continue;
        }
        if (r[x]==r[y])
        {
            cout << 1 << '\n';
            continue;
        }
        if (ancestor(x, y))
            cout << level[x]-level[y] << '\n';
        else
            cout << "impossible" << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 175 ms 17120 KB Output is correct
3 Correct 178 ms 16980 KB Output is correct
4 Correct 177 ms 16976 KB Output is correct
5 Correct 175 ms 16164 KB Output is correct
6 Correct 177 ms 15536 KB Output is correct
7 Correct 201 ms 15192 KB Output is correct
8 Correct 167 ms 10188 KB Output is correct
9 Correct 167 ms 9632 KB Output is correct
10 Correct 177 ms 14928 KB Output is correct
11 Correct 175 ms 13136 KB Output is correct
12 Correct 148 ms 10324 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 16980 KB Output is correct
2 Correct 175 ms 16804 KB Output is correct
3 Correct 175 ms 16980 KB Output is correct
4 Correct 177 ms 9556 KB Output is correct
5 Correct 189 ms 14880 KB Output is correct
6 Incorrect 175 ms 17180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 175 ms 17120 KB Output is correct
3 Correct 178 ms 16980 KB Output is correct
4 Correct 177 ms 16976 KB Output is correct
5 Correct 175 ms 16164 KB Output is correct
6 Correct 177 ms 15536 KB Output is correct
7 Correct 201 ms 15192 KB Output is correct
8 Correct 167 ms 10188 KB Output is correct
9 Correct 167 ms 9632 KB Output is correct
10 Correct 177 ms 14928 KB Output is correct
11 Correct 175 ms 13136 KB Output is correct
12 Correct 148 ms 10324 KB Output is correct
13 Incorrect 1 ms 4440 KB Output isn't correct
14 Halted 0 ms 0 KB -