oj.uz

Submission #714304

# Submission time Handle Problem Language Result Execution time Memory
714304 2023-03-24T08:18:31 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 398172 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;
ll g[N][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 solve()
{
    ll n, q;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
        cin >> a[i].F >> a[i].S;
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++)
    {
        if (i == j)
            g[i][i] = 0;
        elif (sat(a[i], a[j]))
            g[i][j] = 1;
        else
            g[i][j] = 1e9;
    }
    for (ll k = 1; k <= n; k++)
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++)
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    while (q--)
    {
        ll x, y;
        cin >> x >> y;
        if (g[x][y] == 1e9) 
            cout << "impossible\n";
        else
            cout << g[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 1 ms 340 KB Output is correct
2 Runtime error 681 ms 398172 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1277 ms 12212 KB Output is correct
4 Correct 1299 ms 12212 KB Output is correct
5 Correct 1316 ms 12116 KB Output is correct
6 Correct 1309 ms 12212 KB Output is correct
7 Correct 1317 ms 12208 KB Output is correct
8 Correct 1291 ms 12212 KB Output is correct
9 Correct 1295 ms 12212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1277 ms 12212 KB Output is correct
4 Correct 1299 ms 12212 KB Output is correct
5 Correct 1316 ms 12116 KB Output is correct
6 Correct 1309 ms 12212 KB Output is correct
7 Correct 1317 ms 12208 KB Output is correct
8 Correct 1291 ms 12212 KB Output is correct
9 Correct 1295 ms 12212 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1392 ms 12212 KB Output is correct
13 Correct 1371 ms 12216 KB Output is correct
14 Correct 1353 ms 12212 KB Output is correct
15 Correct 1350 ms 12216 KB Output is correct
16 Correct 1374 ms 12212 KB Output is correct
17 Correct 1333 ms 12212 KB Output is correct
18 Correct 1367 ms 12212 KB Output is correct
19 Execution timed out 1586 ms 196228 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1277 ms 12212 KB Output is correct
4 Correct 1299 ms 12212 KB Output is correct
5 Correct 1316 ms 12116 KB Output is correct
6 Correct 1309 ms 12212 KB Output is correct
7 Correct 1317 ms 12208 KB Output is correct
8 Correct 1291 ms 12212 KB Output is correct
9 Correct 1295 ms 12212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1299 ms 12208 KB Output is correct
13 Correct 1320 ms 12212 KB Output is correct
14 Correct 1362 ms 12208 KB Output is correct
15 Correct 1345 ms 12212 KB Output is correct
16 Correct 1343 ms 12212 KB Output is correct
17 Correct 1389 ms 12208 KB Output is correct
18 Correct 1368 ms 12236 KB Output is correct
19 Runtime error 646 ms 398092 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 642 ms 398128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 681 ms 398172 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -