oj.uz

Submission #943768

# Submission time Handle Problem Language Result Execution time Memory
943768 2024-03-11T20:52:35 Z tmarcinkevicius Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 414808 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
typedef pair<int,int> pii;
typedef vector<int> vii;
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define INF 2e18
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())



struct Interval
{
    int id;
    pii range;
};

int N, Q;
vector<Interval> intervals;
vector<pii> queries;

vector<vector<Interval>> adjSorted;
vector<set<int>> adjAll;

int32_t main()
{
    //fast_io();

    cin >> N >> Q;
    intervals = vector<Interval>(N + 1);
    adjAll = vector<set<int>>(N + 1);
    adjSorted = vector<vector<Interval>>(N + 1);

    //vector<pii> endPoints;
    // { time, 0 for start / 1 for end }

    for (int i = 1; i <= N; i++)
    {
        Interval inter;
        cin >> inter.range.f >> inter.range.s;

        inter.id = i;
        intervals[i] = inter;

        //endPoints.push_back({inter.range.f, 0});
        //endPoints.push_back({inter.range.s, 1});
    }

    queries = vector<pii>(Q);
    for (int i = 0; i < Q; i++)
    {
        cin >> queries[i].f >> queries[i].s;
    }

    //sort(all(endPoints));



    //sort(all(intervals), [](Interval a, Interval b)
    //    { return a.range.s < b.range.s; });

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j)
                continue;

            if (intervals[i].range.s >= intervals[j].range.f &&
                intervals[i].range.s <= intervals[j].range.s)
            {
                adjAll[i].insert(j);
            }
        }
    }


    for (int i = 1; i <= N; i++)
    {
        int bestE = -1;
        int bestId = -1;

        //cout << "adjAll[" << i << "]: {";
        for (int j : adjAll[i])
        {
            //cout << j << " ";
            adjSorted[i].push_back(intervals[j]);
        }
        //cout << "}\n";

        sort(all(adjSorted[i]), [](Interval a, Interval b)
            { return a.range.s < b.range.s; });
    }

    for (int q = 0; q < Q; q++)
    {
        if (queries[q].f == queries[q].s)
        {
            cout << 0 << '\n';
            continue;
        }
        vector<int> dis(N + 1, INF);
        queue<int> qu;
        qu.push(queries[q].f);
        dis[queries[q].f] = 0;
        bool impossible = true;

        while (!qu.empty())
        {
            int fr = qu.front();
            qu.pop();
            //cout << "at: " << fr << '\n';

            if (adjAll[fr].count(queries[q].s))
            {
                //cout << "can go already\n";
                cout << dis[fr] + 1 << '\n';
                impossible = false;
                break;
            }

            if (adjSorted[fr].size() == 0)
            {
                continue;
            }

            int low = 0;
            int high = adjSorted[fr].size() - 1;

            while (low < high)
            {
                //cout << "(" << low << " " << high << ")\n";
                int mid = low + (high - low + 1) / 2;

                if (adjSorted[fr][mid].range.s <= intervals[queries[q].s].range.s)
                {
                    low = mid;
                }
                else
                {
                    high = mid - 1;
                }
            }

            Interval bestNode = adjSorted[fr][low];

            if (bestNode.range.s <= intervals[queries[q].s].range.s &&
                dis[bestNode.id] == INF)
            {
                dis[bestNode.id] = dis[fr] + 1;
                qu.push(bestNode.id);
            }
        }

        if (impossible)
        {
            cout << "impossible\n";
        }
    }
}

Compilation message

events.cpp: In function 'int32_t main()':
events.cpp:86:13: warning: unused variable 'bestE' [-Wunused-variable]
   86 |         int bestE = -1;
      |             ^~~~~
events.cpp:87:13: warning: unused variable 'bestId' [-Wunused-variable]
   87 |         int bestId = -1;
      |             ^~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1566 ms 13460 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 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 6 ms 592 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 27 ms 12228 KB Output is correct
7 Correct 64 ms 25428 KB Output is correct
8 Correct 92 ms 38460 KB Output is correct
9 Correct 135 ms 71456 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 6 ms 592 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 27 ms 12228 KB Output is correct
7 Correct 64 ms 25428 KB Output is correct
8 Correct 92 ms 38460 KB Output is correct
9 Correct 135 ms 71456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 580 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 5 ms 548 KB Output is correct
15 Correct 32 ms 12540 KB Output is correct
16 Correct 64 ms 25568 KB Output is correct
17 Correct 90 ms 38480 KB Output is correct
18 Correct 140 ms 71528 KB Output is correct
19 Execution timed out 1589 ms 414808 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 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 6 ms 592 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 27 ms 12228 KB Output is correct
7 Correct 64 ms 25428 KB Output is correct
8 Correct 92 ms 38460 KB Output is correct
9 Correct 135 ms 71456 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 27 ms 12340 KB Output is correct
16 Correct 72 ms 25684 KB Output is correct
17 Correct 91 ms 38608 KB Output is correct
18 Correct 140 ms 71424 KB Output is correct
19 Execution timed out 1511 ms 12124 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1522 ms 13496 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 348 KB Output is correct
2 Execution timed out 1566 ms 13460 KB Time limit exceeded
3 Halted 0 ms 0 KB -