oj.uz

Submission #667038

# Submission time Handle Problem Language Result Execution time Memory
667038 2022-11-30T08:34:03 Z berr Event Hopping (BOI22_events) C++17
0 / 100
 82 ms 12140 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+37;
vector<int> adj[N];
int d[N], p[N], vis[N], c[N];
// 1. subtask

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; cin>>n>>q;

    vector<array<int, 3>> a(n);
    for(int i=0; i<n; i++)
    {
        cin>>a[i][0]>>a[i][1];
        a[i][2]=i; p[i]=i;
    }

    sort(a.begin(), a.end());

    for(int i=0; i<n-1; i++)
    {
        if(a[i+1][0]<=a[i][1]&&a[i+1][1]>=a[i][1])
        {
            adj[a[i][2]].push_back(a[i+1][2]);
            c[a[i+1][2]]++; 
        }
    }

    queue<array<int, 3>> qu; 

    for(int i=0; i<n; i++)
    {
        if(c[i]==0)
        {
            qu.push({i, 0, i});
        }
    }

    while(qu.size())
    {
        int v=qu.front()[0], u=qu.front()[1], par=qu.front()[2];
        qu.pop();
        d[v]=u; p[v]=par;

        if(adj[v].size()) qu.push({adj[v][0], u+1, par});
    }

    while(q--)
    {
        int s, e; cin>>s>>e;
        s--; e--;
        if(p[s]!=p[e]||d[e]<d[s]) cout<<"impossible"<<"\n";
        else cout<<d[e]-d[s]<<"\n";
    }


}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11896 KB Output is correct
2 Correct 82 ms 11764 KB Output is correct
3 Correct 65 ms 11764 KB Output is correct
4 Correct 51 ms 9932 KB Output is correct
5 Correct 67 ms 12140 KB Output is correct
6 Incorrect 73 ms 11968 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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