oj.uz

Submission #714309

# Submission time Handle Problem Language Result Execution time Memory
714309 2023-03-24T08:26:23 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 20428 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 = 6000;
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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Execution timed out 1576 ms 3448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 21 ms 12324 KB Output is correct
4 Correct 15 ms 12388 KB Output is correct
5 Correct 21 ms 12372 KB Output is correct
6 Correct 1277 ms 13944 KB Output is correct
7 Correct 1261 ms 15700 KB Output is correct
8 Correct 1433 ms 17680 KB Output is correct
9 Correct 1234 ms 20428 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 21 ms 12324 KB Output is correct
4 Correct 15 ms 12388 KB Output is correct
5 Correct 21 ms 12372 KB Output is correct
6 Correct 1277 ms 13944 KB Output is correct
7 Correct 1261 ms 15700 KB Output is correct
8 Correct 1433 ms 17680 KB Output is correct
9 Correct 1234 ms 20428 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 12288 KB Output is correct
13 Correct 15 ms 12372 KB Output is correct
14 Correct 22 ms 12492 KB Output is correct
15 Correct 1269 ms 13944 KB Output is correct
16 Correct 1324 ms 15692 KB Output is correct
17 Execution timed out 1503 ms 17676 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 21 ms 12324 KB Output is correct
4 Correct 15 ms 12388 KB Output is correct
5 Correct 21 ms 12372 KB Output is correct
6 Correct 1277 ms 13944 KB Output is correct
7 Correct 1261 ms 15700 KB Output is correct
8 Correct 1433 ms 17680 KB Output is correct
9 Correct 1234 ms 20428 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 19 ms 12352 KB Output is correct
13 Correct 16 ms 12368 KB Output is correct
14 Correct 21 ms 12388 KB Output is correct
15 Correct 1492 ms 13948 KB Output is correct
16 Execution timed out 1580 ms 15568 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 3368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Execution timed out 1576 ms 3448 KB Time limit exceeded
3 Halted 0 ms 0 KB -