oj.uz

Submission #589115

# Submission time Handle Problem Language Result Execution time Memory
589115 2022-07-04T09:28:49 Z radal Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 312884 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){
                if (i == j) continue;
                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> > vec;
        rep(i,1,n+1) vec.pb({a[i],i});
        sort(all(vec),cmp);
        rep(i,0,n) if (par[vec[i].Y] == -1) bfs(vec[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(a[s].Y > a[e].Y){
                cout << "impossible" << 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 289 ms 35284 KB Output is correct
3 Correct 292 ms 35240 KB Output is correct
4 Correct 234 ms 35316 KB Output is correct
5 Incorrect 264 ms 36948 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 4 ms 4992 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 6 ms 5204 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 6 ms 5204 KB Output is correct
6 Correct 10 ms 6068 KB Output is correct
7 Correct 24 ms 7056 KB Output is correct
8 Correct 25 ms 8112 KB Output is correct
9 Correct 13 ms 9044 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 6 ms 5204 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 6 ms 5204 KB Output is correct
6 Correct 10 ms 6068 KB Output is correct
7 Correct 24 ms 7056 KB Output is correct
8 Correct 25 ms 8112 KB Output is correct
9 Correct 13 ms 9044 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5016 KB Output is correct
12 Correct 7 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct
15 Correct 11 ms 6072 KB Output is correct
16 Correct 22 ms 7080 KB Output is correct
17 Correct 26 ms 8132 KB Output is correct
18 Correct 16 ms 9092 KB Output is correct
19 Correct 96 ms 37368 KB Output is correct
20 Correct 33 ms 7708 KB Output is correct
21 Incorrect 34 ms 8140 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 6 ms 5204 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 6 ms 5204 KB Output is correct
6 Correct 10 ms 6068 KB Output is correct
7 Correct 24 ms 7056 KB Output is correct
8 Correct 25 ms 8112 KB Output is correct
9 Correct 13 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 5 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct
15 Correct 10 ms 5972 KB Output is correct
16 Correct 26 ms 6996 KB Output is correct
17 Correct 26 ms 8140 KB Output is correct
18 Correct 13 ms 9044 KB Output is correct
19 Correct 216 ms 34752 KB Output is correct
20 Correct 359 ms 36248 KB Output is correct
21 Execution timed out 1585 ms 312884 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 35272 KB Output is correct
2 Correct 247 ms 35240 KB Output is correct
3 Correct 317 ms 35276 KB Output is correct
4 Correct 260 ms 48360 KB Output is correct
5 Correct 252 ms 35672 KB Output is correct
6 Incorrect 488 ms 74580 KB Output isn't correct
7 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 289 ms 35284 KB Output is correct
3 Correct 292 ms 35240 KB Output is correct
4 Correct 234 ms 35316 KB Output is correct
5 Incorrect 264 ms 36948 KB Output isn't correct
6 Halted 0 ms 0 KB -