oj.uz

Submission #944902

# Submission time Handle Problem Language Result Execution time Memory
944902 2024-03-13T07:43:52 Z tmarcinkevicius Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 71508 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; });

    


    if (N * Q < (int)1e8)
    {

        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";
            }
        }
    }
    else
    {

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

        for (int i = 1; i < N; i++)
        {
            if (intervals[i].range.s >= intervals[i + 1].range.f &&
                intervals[i].range.s <= intervals[i + 1].range.s)
            {
                adjAll[i].insert(i + 1);
            }
        }

        int queueCount = 0;
        vector<pii> QueueIndex(N + 1, {-1, -1});

        for (int i = 1; i <= N; i++)
        {
            if (QueueIndex[i].f != -1)
                continue;

            int qIndex = 0;

            QueueIndex[i].f = queueCount;
            QueueIndex[i].s = qIndex;
            qIndex++;

            queue<int> q;
            q.push(i);

            while (!q.empty())
            {
                int fr = q.front();
                q.pop();

                for (int j : adjAll[fr])
                {
                    if (QueueIndex[j].f != -1)
                        continue;

                    QueueIndex[j].f = queueCount;
                    QueueIndex[j].s = qIndex;
                    qIndex++;
                    q.push(j);
                    break;
                }
            }

            queueCount++;
        }

        /*for (int i = 1; i <= N; i++)
        {
            cout << "{" << QueueIndex[i].f << ", " << QueueIndex[i].s << "}\n";
        }*/

        for (int q = 0; q < Q; q++)
        {
            //cout << "q = " << q << '\n';
            if (QueueIndex[queries[q].f].f != QueueIndex[queries[q].s].f)
            {
                cout << "impossible\n";
                continue;
            }

            cout << abs(QueueIndex[queries[q].f].s - QueueIndex[queries[q].s].s) << '\n';
        }
    }


}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 116 ms 18048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 556 KB Output is correct
6 Correct 27 ms 12192 KB Output is correct
7 Correct 68 ms 25528 KB Output is correct
8 Correct 91 ms 38420 KB Output is correct
9 Correct 141 ms 71508 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 556 KB Output is correct
6 Correct 27 ms 12192 KB Output is correct
7 Correct 68 ms 25528 KB Output is correct
8 Correct 91 ms 38420 KB Output is correct
9 Correct 141 ms 71508 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 27 ms 12152 KB Output is correct
16 Correct 62 ms 25424 KB Output is correct
17 Correct 92 ms 38484 KB Output is correct
18 Correct 139 ms 71504 KB Output is correct
19 Incorrect 42 ms 3156 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 556 KB Output is correct
6 Correct 27 ms 12192 KB Output is correct
7 Correct 68 ms 25528 KB Output is correct
8 Correct 91 ms 38420 KB Output is correct
9 Correct 141 ms 71508 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 4 ms 520 KB Output is correct
15 Correct 27 ms 12124 KB Output is correct
16 Correct 62 ms 25428 KB Output is correct
17 Correct 91 ms 38364 KB Output is correct
18 Correct 149 ms 71508 KB Output is correct
19 Execution timed out 1516 ms 9968 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 18000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 116 ms 18048 KB Output isn't correct
3 Halted 0 ms 0 KB -