oj.uz

답안 #697806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697806 2023-02-11T06:25:17 Z Duy_e Event Hopping (BOI22_events) C++14
0 / 100
 7 ms 12136 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 1e5 + 5;

ll n, q, s[N], e[N];
vector <int> cmp, out[2 * N], in[2 * N];
vector <int> d[N];

const ll Nmax = 5005;
int dist[Nmax][Nmax];
void bfs(int st, int *f) {
    rep(i, 1, n) f[i] = 1e9;
    f[st] = 0;
    queue <int> q;
    q.push(st);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int v: d[u]) if (f[v] > f[u] + 1) {
            f[v] = f[u] + 1;
            q.push(v);
        }
    }
}

namespace sub4 {

    pii a[N];
    ll pos[N], f[N];
    void solve() {
        rep(i, 1, n) a[i] = {e[i], i};
        sort(a + 1, a + 1 + n);
        rep(i, 1, n) pos[a[i].nd] = i;
        while (q --) {
            int u, v;
            cin >> u >> v;
            int i = pos[u];
            int j = pos[v];
            int l = j;

            if (i > j && a[j].st < a[i].st) {
                cout << "impossible\n";
                continue;
            }

            if (i > j) {
                cout << 1 << '\n';
                continue;
            }

            while (l + 1 <= n && a[l + 1].st == a[j].st) l ++;

            f[l + 1] = 1e9;
            //cout << i << ' ' << j << '\n';
            rrep(k, l, i) {
                int id = a[k].nd;
                f[k] = min(f[k + 1], s[id]);
            }
            int ans = 0;
            while (i < j) {
                ans ++;
                int cur = a[i].st, pre = i;
                while (i < l && cur >= f[i + 1]) {
                    i ++;
                }
                if (i > j) {
                    int id = a[j].nd;
                    if (cur >= s[v] && cur <= e[v])
                        break;
                    ans ++;
                    break;
                }
                if (i == pre) break;

            }

            //cout << i << ' ' << j << '\n';

            if (i >= j)
                cout << ans << '\n';
            else
                cout << "impossible\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen("events.inp", "r", stdin);
    freopen("events.out", "w", stdout);

    cin >> n >> q;
    rep(i, 1, n)
        cin >> s[i] >> e[i];

    if (q <= 100) {
        sub4 :: solve();
        return 0;
    }

    rep(i, 1, n) rep(j, 1, n) if (i != j)
        if (s[j] <= e[i] && e[i] <= e[j])
            d[i].push_back(j);

    rep(i, 1, n) bfs(i, dist[i]);

    while (q --) {
        int u, v;
        cin >> u >> v;
        if (dist[u][v] >= (int)1e9)
            cout << "impossible\n";
        else
            cout << dist[u][v] << '\n';
    }

    return 0;
}

Compilation message

events.cpp: In function 'void sub4::solve()':
events.cpp:74:25: warning: unused variable 'id' [-Wunused-variable]
   74 |                     int id = a[j].nd;
      |                         ^~
events.cpp: In function 'int main()':
events.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     freopen("events.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     freopen("events.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12116 KB Output isn't correct
2 Halted 0 ms 0 KB -