oj.uz

Submission #944892

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


    if (N * Q < (int)1e7)
    {
        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
    {
        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: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 344 KB Output is correct
2 Execution timed out 1559 ms 14704 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 348 KB Output is correct
3 Correct 6 ms 444 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 30 ms 12340 KB Output is correct
7 Correct 63 ms 25576 KB Output is correct
8 Correct 91 ms 38344 KB Output is correct
9 Correct 149 ms 71420 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 348 KB Output is correct
3 Correct 6 ms 444 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 30 ms 12340 KB Output is correct
7 Correct 63 ms 25576 KB Output is correct
8 Correct 91 ms 38344 KB Output is correct
9 Correct 149 ms 71420 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 27 ms 12380 KB Output is correct
16 Correct 62 ms 25428 KB Output is correct
17 Correct 92 ms 38508 KB Output is correct
18 Correct 148 ms 71508 KB Output is correct
19 Incorrect 1250 ms 415468 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 444 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 30 ms 12340 KB Output is correct
7 Correct 63 ms 25576 KB Output is correct
8 Correct 91 ms 38344 KB Output is correct
9 Correct 149 ms 71420 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 6 ms 560 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 36 ms 12380 KB Output is correct
16 Correct 64 ms 25684 KB Output is correct
17 Correct 97 ms 38484 KB Output is correct
18 Correct 142 ms 71528 KB Output is correct
19 Execution timed out 1512 ms 12088 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 1572 ms 14924 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 344 KB Output is correct
2 Execution timed out 1559 ms 14704 KB Time limit exceeded
3 Halted 0 ms 0 KB -