oj.uz

Submission #589043

# Submission time Handle Problem Language Result Execution time Memory
589043 2022-07-04T09:00:27 Z radal Event Hopping (BOI22_events) C++17
10 / 100
 313 ms 35460 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+10,mod = 1e9+7,inf = 1e9+10,sq = 90;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int nxt[N][20];
pll a[N];
int par[N],d[N];
vector<int> adj[N];
map<int,vector<int>> st,en;
void bfs(int v){
    par[v] = v;
    d[v] = 0;
    queue<int> q;
    q.push(v);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int w : adj[u]){
            if (par[w] == -1){
                par[w] = v;
                d[w] = d[u]+1;
                q.push(w);
            }
        }
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    vector<int> ve;
    rep(i,1,n+1){
        cin >> a[i].X >> a[i].Y;
        ve.pb(a[i].X);
        ve.pb(a[i].Y);
        st[a[i].X].pb(i);
        en[a[i].Y].pb(i);
    }
    set<int> cur;
    sort(all(ve));
    int perv = -1;
    for (int u : ve){
        if (u == perv) continue;
        perv = u;
        for (int i : st[u]) cur.insert(i);
        for (int i : en[u]){
            for (int j : cur){
                adj[i].pb(j);
            }
        }
        for (int i : en[u]) cur.erase(i);
    }
    if (n <= 1000 && q <= 100){
        rep(i,0,q){
            int s,e;
            cin >> s >> e;
            if (s == e){
                cout << 0 << endl;
                continue;
            }
            if (a[s].Y == a[e].Y){
                cout << 1 << endl;
                continue;
            }
            rep(i,1,n+1) par[i] = -1;
            bfs(s);
            if (par[e] == -1) cout << "impossible" << endl;
            else cout << d[e] << endl;
            continue;
        }
    }
    else{
        memset(par,-1,sizeof par);
        rep(i,1,n+1) if (par[i] == -1) bfs(i);
        while (q--){
            int s,e;
            cin >> s >> e;
            if (s == e){
                cout << 0 << endl;
                continue;
            }
            if (a[s].Y == a[e].Y){
                cout << 1 << endl;
                continue;
            }
            if (par[s] != par[e])
                cout << "impossible" << endl;
            else
                cout << d[e]-d[s] << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2968 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 12 ms 3740 KB Output is correct
7 Correct 22 ms 4620 KB Output is correct
8 Correct 28 ms 5708 KB Output is correct
9 Correct 11 ms 6740 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2968 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 12 ms 3740 KB Output is correct
7 Correct 22 ms 4620 KB Output is correct
8 Correct 28 ms 5708 KB Output is correct
9 Correct 11 ms 6740 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 6 ms 2900 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 4 ms 2968 KB Output is correct
15 Correct 8 ms 3668 KB Output is correct
16 Correct 20 ms 4692 KB Output is correct
17 Correct 27 ms 5716 KB Output is correct
18 Correct 11 ms 6748 KB Output is correct
19 Incorrect 98 ms 35460 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2968 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 12 ms 3740 KB Output is correct
7 Correct 22 ms 4620 KB Output is correct
8 Correct 28 ms 5708 KB Output is correct
9 Correct 11 ms 6740 KB Output is correct
10 Correct 2 ms 2576 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 4 ms 2900 KB Output is correct
14 Correct 4 ms 2900 KB Output is correct
15 Correct 8 ms 3736 KB Output is correct
16 Correct 19 ms 4692 KB Output is correct
17 Correct 28 ms 5692 KB Output is correct
18 Correct 11 ms 6688 KB Output is correct
19 Incorrect 246 ms 30260 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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