oj.uz

Submission #580311

# Submission time Handle Problem Language Result Execution time Memory
580311 2022-06-21T05:08:56 Z 반딧불(#8355) Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 130480 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Range{
    int l, r, idx;
    Range(){}
    Range(int l, int r, int idx): l(l), r(r), idx(idx){}
    bool operator<(const Range &nxt)const{
        return l<nxt.l;
    }
};

struct dat{
    int s, x, idx;
    dat(){}
    dat(int s, int x, int idx): s(s), x(x), idx(idx){}
    bool operator<(const dat &r)const{
        return s<r.s;
    }
};

int n, q;
Range arr[100002];
vector<int> link[100002];
int dist[5002][5002];

void bfs(int r){
    queue<pair<int, int> > que;
    que.push(make_pair(r, 0));
    while(!que.empty()){
        int x = que.front().first, d = que.front().second;
        que.pop();
        for(auto y: link[x]){
            if(dist[r][y] != 1e9) continue;
            dist[r][y] = d+1;
            que.push(make_pair(y, d+1));
        }
    }
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].l, &arr[i].r);
        arr[i].idx = i;
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        if(i==j) continue;
        if(arr[j].l <= arr[i].r && arr[i].r <= arr[j].r) link[i].push_back(j);
        dist[i][j] = 1e9;
    }
    for(int i=1; i<=n; i++) bfs(i);

    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        if(dist[l][r] == 1e9) printf("impossible\n");
        else printf("%d\n", dist[l][r]);
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d", &arr[i].l, &arr[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1590 ms 57300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 25 ms 10652 KB Output is correct
4 Correct 20 ms 10548 KB Output is correct
5 Correct 32 ms 10656 KB Output is correct
6 Correct 66 ms 11428 KB Output is correct
7 Correct 144 ms 12232 KB Output is correct
8 Correct 151 ms 13268 KB Output is correct
9 Correct 898 ms 14640 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 25 ms 10652 KB Output is correct
4 Correct 20 ms 10548 KB Output is correct
5 Correct 32 ms 10656 KB Output is correct
6 Correct 66 ms 11428 KB Output is correct
7 Correct 144 ms 12232 KB Output is correct
8 Correct 151 ms 13268 KB Output is correct
9 Correct 898 ms 14640 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 26 ms 10548 KB Output is correct
13 Correct 22 ms 10580 KB Output is correct
14 Correct 29 ms 10648 KB Output is correct
15 Correct 61 ms 11332 KB Output is correct
16 Correct 136 ms 12236 KB Output is correct
17 Correct 161 ms 13292 KB Output is correct
18 Correct 881 ms 14636 KB Output is correct
19 Execution timed out 1576 ms 130480 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 25 ms 10652 KB Output is correct
4 Correct 20 ms 10548 KB Output is correct
5 Correct 32 ms 10656 KB Output is correct
6 Correct 66 ms 11428 KB Output is correct
7 Correct 144 ms 12232 KB Output is correct
8 Correct 151 ms 13268 KB Output is correct
9 Correct 898 ms 14640 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 27 ms 10628 KB Output is correct
13 Correct 22 ms 10664 KB Output is correct
14 Correct 28 ms 10612 KB Output is correct
15 Correct 53 ms 11348 KB Output is correct
16 Correct 137 ms 12364 KB Output is correct
17 Correct 196 ms 13292 KB Output is correct
18 Correct 825 ms 14668 KB Output is correct
19 Execution timed out 1579 ms 57720 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1597 ms 56764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1590 ms 57300 KB Time limit exceeded
3 Halted 0 ms 0 KB -