oj.uz

답안 #714308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714308 2023-03-24T08:25:12 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250824 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 5005, MAX = 10000;
ll dist[N][N], n;
vv(ll) g[N];
pp(ll, ll) a[N];
bool sat(pp(ll, ll) a, pp(ll, ll) b)
{
    return b.F <= a.S and a.S <= b.S;
}
void bfs(ll st)
{
    for (ll i = 1; i <= n; i++)
        dist[st][i] = 1e9;
    dist[st][st] = 0;
    qq(ll) q;
    q.push(st);
    while (!q.empty())
    {
        ll v = q.front();
        q.pop();
        for (ll to : g[v])
            if (dist[st][to] == 1e9)
            {
                dist[st][to] = dist[st][v] + 1;
                q.push(to);
            }
    }
}
void solve()
{
    ll q;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
        cin >> a[i].F >> a[i].S;
    ll m = 0;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++)
        {
            if (i == j)
                dist[i][i] = 0;
            elif (sat(a[i], a[j]))
                dist[i][j] = 1, g[i].pb(j),
                m++;
            else dist[i][j] = 1e9;
        }
    if (m > MAX)
    {
        for (ll k = 1; k <= n; k++)
            for (ll i = 1; i <= n; i++)
                for (ll j = 1; j <= n; j++)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    else
    {
        for (ll i = 1; i <= n; i++)
            bfs(i);
    }
    while (q--)
    {
        ll x, y;
        cin >> x >> y;
        if (dist[x][y] == 1e9)
            cout << "impossible\n";
        else
            cout << dist[x][y] << endl;
    }
}
/*

*/
int main()
{
    sync
        // precomp();
        ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case " << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Execution timed out 1569 ms 3412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 19 ms 12388 KB Output is correct
4 Correct 16 ms 12340 KB Output is correct
5 Correct 21 ms 12360 KB Output is correct
6 Correct 1285 ms 13944 KB Output is correct
7 Correct 1401 ms 15588 KB Output is correct
8 Correct 1338 ms 17676 KB Output is correct
9 Correct 1329 ms 20376 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 19 ms 12388 KB Output is correct
4 Correct 16 ms 12340 KB Output is correct
5 Correct 21 ms 12360 KB Output is correct
6 Correct 1285 ms 13944 KB Output is correct
7 Correct 1401 ms 15588 KB Output is correct
8 Correct 1338 ms 17676 KB Output is correct
9 Correct 1329 ms 20376 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 20 ms 12388 KB Output is correct
13 Correct 16 ms 12304 KB Output is correct
14 Correct 21 ms 12384 KB Output is correct
15 Correct 1365 ms 13944 KB Output is correct
16 Correct 1260 ms 15592 KB Output is correct
17 Correct 1369 ms 17684 KB Output is correct
18 Correct 1233 ms 20380 KB Output is correct
19 Execution timed out 1537 ms 250824 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 19 ms 12388 KB Output is correct
4 Correct 16 ms 12340 KB Output is correct
5 Correct 21 ms 12360 KB Output is correct
6 Correct 1285 ms 13944 KB Output is correct
7 Correct 1401 ms 15588 KB Output is correct
8 Correct 1338 ms 17676 KB Output is correct
9 Correct 1329 ms 20376 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 19 ms 12268 KB Output is correct
13 Correct 15 ms 12316 KB Output is correct
14 Correct 21 ms 12388 KB Output is correct
15 Correct 1316 ms 13944 KB Output is correct
16 Correct 1373 ms 15592 KB Output is correct
17 Correct 1292 ms 17676 KB Output is correct
18 Correct 1281 ms 20376 KB Output is correct
19 Execution timed out 1588 ms 1772 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1579 ms 3420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Execution timed out 1569 ms 3412 KB Time limit exceeded
3 Halted 0 ms 0 KB -