oj.uz

답안 #714296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714296 2023-03-24T08:10:27 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 399728 KB 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define ll          long long 
#define ull         unsigned long long 
#define ld          long double 
#define ui          unsigned int 
#define f           first
#define s           second
#define ins         insert
#define pb          push_back
#define mp          make_pair
#define ln          '\n'
#define int         ll
#define pii         pair<int , int> 
#define INF         LLONG_MAX
#define vv(a)       vector<a>
#define pp(a, b)    pair<a, b>
#define pq(a)       priority_queue<a>
#define qq(a)       queue<a>
#define ss(a)       set<a>
#define mss(a)      multiset<a>
#define mm(a, b)    map<a, b>
#define mmm(a , b)  multimap<a , b>
#define sz(x)       (x).size()
#define all(x)      (x).begin() , (x).end()
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

const int MAX = 5010;
vv(pii) a(MAX);
vv(vv(int)) g(MAX);
vv(vv(int)) dist(MAX , vv(int) (MAX , -1));

void BFS(int node){
    dist[node][node] = 0;
    queue<int> Q;   
    Q.push(node);
    while(!Q.empty()){
        int from = Q.front();
        Q.pop();
        for(auto to : g[from]){
            if(dist[node][to] == -1){
                dist[node][to] = dist[node][from] + 1;
                Q.push(to);
            }
        }
    }
}

void solve(){
    int n , q;
    cin >> n >> q;
    for(int i=0 ; i<n ; i++){
        cin >> a[i].f >> a[i].s;
    }   
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<n ; j++){
            if(i != j){
                if(a[j].f <= a[i].s && a[j].s >= a[i].s){
                    g[i].pb(j);
                }
            }
        }
    }
    for(int i=0 ; i<n ; i++){
        BFS(i);
    }
    //cout << dist[0][3] << ln;
    for(int i=0 ; i<q ; i++){
        int u , v;
        cin >> u >> v;
        u--; v--;
        if(dist[u][v] == -1){
            cout << "impossible" << ln;
        }
        else{
            cout << dist[u][v] << ln;
        }
    }
}


signed main(){
    fastio

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 197196 KB Output is correct
2 Runtime error 244 ms 399680 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 197196 KB Output is correct
2 Correct 101 ms 197080 KB Output is correct
3 Correct 93 ms 197104 KB Output is correct
4 Correct 89 ms 197140 KB Output is correct
5 Correct 91 ms 197108 KB Output is correct
6 Correct 141 ms 198800 KB Output is correct
7 Correct 251 ms 200432 KB Output is correct
8 Correct 286 ms 202492 KB Output is correct
9 Correct 1248 ms 205280 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 197196 KB Output is correct
2 Correct 101 ms 197080 KB Output is correct
3 Correct 93 ms 197104 KB Output is correct
4 Correct 89 ms 197140 KB Output is correct
5 Correct 91 ms 197108 KB Output is correct
6 Correct 141 ms 198800 KB Output is correct
7 Correct 251 ms 200432 KB Output is correct
8 Correct 286 ms 202492 KB Output is correct
9 Correct 1248 ms 205280 KB Output is correct
10 Correct 92 ms 197092 KB Output is correct
11 Correct 89 ms 197180 KB Output is correct
12 Correct 97 ms 197200 KB Output is correct
13 Correct 93 ms 197148 KB Output is correct
14 Correct 97 ms 197216 KB Output is correct
15 Correct 138 ms 198768 KB Output is correct
16 Correct 260 ms 200436 KB Output is correct
17 Correct 332 ms 202492 KB Output is correct
18 Correct 1277 ms 205228 KB Output is correct
19 Execution timed out 1592 ms 251468 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 197196 KB Output is correct
2 Correct 101 ms 197080 KB Output is correct
3 Correct 93 ms 197104 KB Output is correct
4 Correct 89 ms 197140 KB Output is correct
5 Correct 91 ms 197108 KB Output is correct
6 Correct 141 ms 198800 KB Output is correct
7 Correct 251 ms 200432 KB Output is correct
8 Correct 286 ms 202492 KB Output is correct
9 Correct 1248 ms 205280 KB Output is correct
10 Correct 78 ms 197096 KB Output is correct
11 Correct 80 ms 197148 KB Output is correct
12 Correct 94 ms 197108 KB Output is correct
13 Correct 90 ms 197252 KB Output is correct
14 Correct 91 ms 197184 KB Output is correct
15 Correct 130 ms 198752 KB Output is correct
16 Correct 249 ms 200392 KB Output is correct
17 Correct 270 ms 202572 KB Output is correct
18 Correct 1277 ms 205228 KB Output is correct
19 Runtime error 243 ms 399544 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 266 ms 399728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 197196 KB Output is correct
2 Runtime error 244 ms 399680 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -