oj.uz

Submission #670325

# Submission time Handle Problem Language Result Execution time Memory
670325 2022-12-08T17:06:08 Z efedmrlr Event Hopping (BOI22_events) C++17
10 / 100
 208 ms 11500 KB 
#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back

using namespace std;

const int N = 1e3+5;
const int Q = 105;
const int MOD = 1e9+7;

int n,m,q;
vector<pair<int,int> > events;
vector<int> adj[N];
vector<pair<int,int> > queries(Q);
bool vis[N];
int bfs(int x, int y) {
    queue<int> nodes;
    nodes.push(x);
    nodes.push(-1);
    for (int i = 1; i <= n; i++)
    {
        vis[i] = false;
    }
    int dist = 0;
    int cur;
    while (nodes.size() > 1) {
        cur = nodes.front();
        nodes.pop();
        if(cur==-1) {
            dist++;
            nodes.push(-1);
            continue;
        }
        if(cur == y) {
            return dist;
        }
        if(vis[cur]) continue;
        vis[cur] = true;
        for (int i = 0; i < adj[cur].size(); i++)
        {
            if(vis[adj[cur][i]]) continue;
            nodes.push(adj[cur][i]);
        }
        
    }
    return -1;
}

void solve() {
    cin>>n>>q;
    events.pb(MP(-1,-1));
    for (int i = 1; i <= n; i++)
    {
        int tmp1,tmp2;
        cin>>tmp1>>tmp2;
        events.pb(MP(tmp1,tmp2));

    }
    for (int i = 0; i < q; i++)
    {
        cin>>queries[i].first>>queries[i].second;
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = i+1; j <= n; j++)
        {

            if(events[i].second > events[j].second &&
                 events[j].second >= events[i].first) {
                adj[j].pb(i);
                //cout<<j<<" >> "<<i<<"\n";
            }
            else if(events[j].second > events[i].second &&
                     events[i].second >= events[j].first) {
                adj[i].pb(j);
                //cout<<i<<" >> "<<j<<"\n";
            }
            else if(events[j].second == events[i].second) {
                adj[i].pb(j); adj[j].pb(i);
            }
        }
        
    }
    int res;
    for (int i = 0; i < q; i++)
    {
        res = bfs(queries[i].first,queries[i].second);
        if(res==-1) cout<<"impossible\n";
        else cout<<res<<"\n";  
    }
    


    


    
}

signed main() {
    solve();
}

Compilation message

events.cpp: In function 'long long int bfs(long long int, long long int)':
events.cpp:40:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < adj[cur].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 78 ms 6148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 15 ms 2188 KB Output is correct
7 Correct 53 ms 4912 KB Output is correct
8 Correct 46 ms 7740 KB Output is correct
9 Correct 179 ms 11488 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 15 ms 2188 KB Output is correct
7 Correct 53 ms 4912 KB Output is correct
8 Correct 46 ms 7740 KB Output is correct
9 Correct 179 ms 11488 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 15 ms 2120 KB Output is correct
16 Correct 53 ms 4760 KB Output is correct
17 Correct 42 ms 7780 KB Output is correct
18 Correct 178 ms 11472 KB Output is correct
19 Runtime error 8 ms 1204 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 15 ms 2188 KB Output is correct
7 Correct 53 ms 4912 KB Output is correct
8 Correct 46 ms 7740 KB Output is correct
9 Correct 179 ms 11488 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 5 ms 380 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 14 ms 2188 KB Output is correct
16 Correct 48 ms 4836 KB Output is correct
17 Correct 42 ms 7736 KB Output is correct
18 Correct 208 ms 11500 KB Output is correct
19 Runtime error 73 ms 5748 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 6108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 78 ms 6148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -