Submission #809196

#	Time	Username	Problem	Language	Result	Execution time	Memory
809196		thimote75	Event Hopping (BOI22_events)	C++14	0 / 100	1564 ms	2240 KiB

events

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> timings;
vector<pair<int, int>> events;

using idata = vector<int>;

int main () {
    int N, Q;
    cin >> N >> Q;

    for (int i = 0; i < N; i ++) {
        int a, b;
        cin >> a >> b;

        events.push_back({ a, b });

        timings.push_back({ b, i });
    }

    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        idata dp(N, 1e9);
        dp[a] = 0;
        
        for (const auto &timing : timings) {
            for (int i = 0; i < N; i ++) {
                if (i == timing.second) continue ;
            
                if (events[i].second < timing.first
                 || events[i].first  > timing.first) continue ;
                dp[i] = min(dp[i], dp[timing.second] + 1);
            }
        }
        
        if (dp[b] > N) cout << "impossible\n";
        else cout << dp[b] << "\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30