oj.uz

Submission #646022

# Submission time Handle Problem Language Result Execution time Memory
646022 2022-09-28T13:57:24 Z GaLz Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 130732 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=1e5+5;
const int INF=1e8;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
vi adj[maxn];
int n, q, dis[5001][5001], u, v;
pii arr[maxn];
int main() {
    ok
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> arr[i].fi >> arr[i].se;
    if(n<=5000) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(i==j) continue;
                if(arr[i].se>=arr[j].fi && arr[i].se<=arr[j].se) adj[i].pb(j);
            }
        }
        memset(dis, -1, sizeof dis);
        for(int i=1; i<=n; i++) {
            dis[i][i]=0;
            queue<int> qu;
            qu.push(i);
            while(!qu.empty()) {
                int fr=qu.front(); qu.pop();
                for(auto it : adj[fr]) {
                    if(dis[i][it]==-1) {
                        dis[i][it]=dis[i][fr]+1;
                        qu.push(it);
                    }
                }
            }
        }
        while(q--) {
            cin >> u >> v;
            if(dis[u][v]==-1) cout << "impossible";
            else cout << dis[u][v];
            cout << endl;
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100436 KB Output is correct
2 Incorrect 18 ms 3432 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 48 ms 100536 KB Output is correct
2 Correct 38 ms 100464 KB Output is correct
3 Correct 55 ms 100600 KB Output is correct
4 Correct 54 ms 100604 KB Output is correct
5 Correct 51 ms 100512 KB Output is correct
6 Correct 85 ms 101392 KB Output is correct
7 Correct 180 ms 102192 KB Output is correct
8 Correct 202 ms 103152 KB Output is correct
9 Correct 935 ms 104596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100536 KB Output is correct
2 Correct 38 ms 100464 KB Output is correct
3 Correct 55 ms 100600 KB Output is correct
4 Correct 54 ms 100604 KB Output is correct
5 Correct 51 ms 100512 KB Output is correct
6 Correct 85 ms 101392 KB Output is correct
7 Correct 180 ms 102192 KB Output is correct
8 Correct 202 ms 103152 KB Output is correct
9 Correct 935 ms 104596 KB Output is correct
10 Correct 38 ms 100428 KB Output is correct
11 Correct 44 ms 100440 KB Output is correct
12 Correct 53 ms 100556 KB Output is correct
13 Correct 45 ms 100576 KB Output is correct
14 Correct 53 ms 100500 KB Output is correct
15 Correct 89 ms 101384 KB Output is correct
16 Correct 188 ms 102200 KB Output is correct
17 Correct 211 ms 103248 KB Output is correct
18 Correct 999 ms 104600 KB Output is correct
19 Execution timed out 1582 ms 130732 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100536 KB Output is correct
2 Correct 38 ms 100464 KB Output is correct
3 Correct 55 ms 100600 KB Output is correct
4 Correct 54 ms 100604 KB Output is correct
5 Correct 51 ms 100512 KB Output is correct
6 Correct 85 ms 101392 KB Output is correct
7 Correct 180 ms 102192 KB Output is correct
8 Correct 202 ms 103152 KB Output is correct
9 Correct 935 ms 104596 KB Output is correct
10 Correct 53 ms 100428 KB Output is correct
11 Correct 38 ms 100428 KB Output is correct
12 Correct 52 ms 100540 KB Output is correct
13 Correct 60 ms 100500 KB Output is correct
14 Correct 62 ms 100592 KB Output is correct
15 Correct 82 ms 101388 KB Output is correct
16 Correct 192 ms 102092 KB Output is correct
17 Correct 209 ms 103256 KB Output is correct
18 Correct 895 ms 104604 KB Output is correct
19 Incorrect 22 ms 5284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100436 KB Output is correct
2 Incorrect 18 ms 3432 KB Output isn't correct
3 Halted 0 ms 0 KB -