Submission #697930

#	Time	Username	Problem	Language	Result	Execution time	Memory
697930		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1583 ms	128660 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define fi first
#define se second
#define sz(x) (int)x.size()
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rrep(i, b, e) for (int i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 5e3 + 7;

int n, q, s[N], e[N];

void read() {
    cin >> n >> q;
    rep(i, 1, n) cin >> s[i] >> e[i];
}

int d[N][N];
vector<int> adj[N];
void sub3() {
    rep(i, 1, n) rep(j, 1, n) {
        if (s[j] <= e[i] && e[i] <= e[j]) {
            adj[i].push_back(j);
        }
    }

    memset(d, -1, sizeof d);
    rep(i, 1, n) {
        queue<int> q;
        q.push(i); d[i][i] = 0;
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v: adj[u]) if (d[i][v] == -1) {
                d[i][v] = d[i][u] + 1;
                q.push(v);
            }
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        (d[l][r] == -1 ? cout << "impossible\n" : cout << d[l][r] << '\n');
    }
}

void solve() {
    if (n <= 5000) sub3();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    read();
    solve();
}


/**
+ check mod (gõ đúng số), limit, kiểu dữ liệu
+ check format output
+mấy bài multitest:
    quên reset biến, mảng, (nên dùng fill, memset, v.v)
    quên xuống dòng
    precompute đầu bài
+nhập hết dữ liệu trước khi return
+xóa debug
**/

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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