oj.uz

Submission #589073

# Submission time Handle Problem Language Result Execution time Memory
589073 2022-07-04T09:10:59 Z radal Event Hopping (BOI22_events) C++17
10 / 100
 324 ms 52052 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 = 2e5+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; 
}
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);
            }
        }
    }
}
inline bool cmp(pair<pll,int> x,pair<pll,int> y){
    if (x.X.Y != y.X.Y) return (x.X.Y < y.X.Y);
    return (x < y);
}
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);
        vector<pair<pll,int> > ve;
        rep(i,1,n+1) ve.pb({a[i],i});
        sort(all(ve),cmp);
        rep(i,0,n) if (par[ve[i].Y] == -1) bfs(ve[i].Y);
        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 3 ms 4948 KB Output is correct
2 Correct 272 ms 35664 KB Output is correct
3 Correct 317 ms 36196 KB Output is correct
4 Correct 244 ms 36180 KB Output is correct
5 Incorrect 257 ms 37852 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 10 ms 5972 KB Output is correct
7 Correct 19 ms 6980 KB Output is correct
8 Correct 24 ms 8144 KB Output is correct
9 Correct 11 ms 9044 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 10 ms 5972 KB Output is correct
7 Correct 19 ms 6980 KB Output is correct
8 Correct 24 ms 8144 KB Output is correct
9 Correct 11 ms 9044 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5204 KB Output is correct
15 Correct 9 ms 6080 KB Output is correct
16 Correct 21 ms 7192 KB Output is correct
17 Correct 25 ms 8152 KB Output is correct
18 Correct 12 ms 9032 KB Output is correct
19 Correct 104 ms 37848 KB Output is correct
20 Correct 33 ms 8592 KB Output is correct
21 Incorrect 33 ms 8508 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 10 ms 5972 KB Output is correct
7 Correct 19 ms 6980 KB Output is correct
8 Correct 24 ms 8144 KB Output is correct
9 Correct 11 ms 9044 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 6 ms 5204 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5204 KB Output is correct
15 Correct 9 ms 5972 KB Output is correct
16 Correct 20 ms 6988 KB Output is correct
17 Correct 25 ms 8148 KB Output is correct
18 Correct 11 ms 9040 KB Output is correct
19 Correct 252 ms 35900 KB Output is correct
20 Incorrect 324 ms 36600 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 35772 KB Output is correct
2 Correct 240 ms 36232 KB Output is correct
3 Correct 264 ms 36112 KB Output is correct
4 Correct 287 ms 52052 KB Output is correct
5 Incorrect 276 ms 36432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 272 ms 35664 KB Output is correct
3 Correct 317 ms 36196 KB Output is correct
4 Correct 244 ms 36180 KB Output is correct
5 Incorrect 257 ms 37852 KB Output isn't correct
6 Halted 0 ms 0 KB -