oj.uz

답안 #877452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877452 2023-11-23T08:46:51 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250732 KB 
///#include "art.h"
#include <bits/stdc++.h>

using namespace std;

const long long maxn = 1e5;
const long long mod = 1e9+7;
const long long logn=30;

int main()
{
    ios::sync_with_stdio(false);
    long long n,q;
    cin>>n>>q;
    vector<pair<long long,long long>>v;
    for(long long i=0;i<n;i++)
    {
        long long x,y;
        cin>>x>>y;
        v.push_back({x,y});
    }
    vector<long long>g[n];
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<n;j++)
        {
            if(j==i)continue;
            if(v[j].first<=v[i].second)
            {
                if(v[j].second>=v[i].second)
                {
                    g[i].push_back(j);
                }
            }
        }
    }
    /*if(n<1005)
    {
        while(q--)
        {
            long long ans=-1;
            long long l,r;
            cin>>l>>r;
            l--;r--;
            bool vis[n];
            memset(vis,0,sizeof vis);
            queue<long long>Q;
            Q.push(l);
            Q.push(0);
            vis[l]=true;
            while(!Q.empty())
            {
                long long teme=Q.front();
                Q.pop();
                long long k=Q.front();Q.pop();
                if(teme==r)
                {
                    ans=k;
                    break;
                }
                for(auto ax:g[teme])
                {
                    if(vis[ax])continue;
                    Q.push(ax);
                    Q.push(k+1);
                    vis[ax]=true;
                }
            }
            if(ans==-1)
            {
                cout<<"impossible"<<endl;
            }
            else
            {
                cout<<ans<<endl;
            }
        }
        return 0;
    }*/
    long long dis[n][n];
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<n;j++)
        {
            dis[i][j]=2e9;
        }
    }
    for(long long i=0;i<n;i++)
    {
            dis[i][i]=0;
            bool vis[n];
            memset(vis,0,sizeof vis);
            queue<long long>Q;
            Q.push(i);
            Q.push(0);
            Q.push(-1);
            vis[i]=true;
            while(!Q.empty())
            {
                long long teme=Q.front();
                Q.pop();
                long long k=Q.front();Q.pop();
                long long prev=Q.front();Q.pop();
                if(teme!=i)
                {
                    dis[i][teme]=min(dis[i][teme], k);
                }
                for(auto ax:g[teme])
                {
                    if(prev==ax || vis[ax]==true)continue;
                    Q.push(ax);
                    Q.push(k+1);
                    Q.push(teme);
                    vis[ax]=true;
                }
            }
    }
    while(q--)
    {
        long long l,r;
        cin>>l>>r;
        l--;r--;
        if(dis[l][r]==2e9)
        {
            cout<<"impossible"<<endl;
        }
        else
        {
            cout<<dis[l][r]<<endl;
        }
    }
    return 0;
}


/*
void solve(long long n)
{
    if(n<=6)
    {
        vector<long long>v;
        for(long long i=1;i<=n;i++)
        {
            v.push_back(i);
        }
        do
        {
            long long kol=publish(v);
            if(kol==0)
            {
                answer(v);
            }
        }while(next_permutation(v.begin(),v.end()));
    }


   /// publish(order);
   /// answer(order);
}

*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1546 ms 4308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 16 ms 8284 KB Output is correct
4 Correct 13 ms 8284 KB Output is correct
5 Correct 18 ms 8356 KB Output is correct
6 Correct 45 ms 9820 KB Output is correct
7 Correct 111 ms 11516 KB Output is correct
8 Correct 130 ms 13660 KB Output is correct
9 Correct 675 ms 16372 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 16 ms 8284 KB Output is correct
4 Correct 13 ms 8284 KB Output is correct
5 Correct 18 ms 8356 KB Output is correct
6 Correct 45 ms 9820 KB Output is correct
7 Correct 111 ms 11516 KB Output is correct
8 Correct 130 ms 13660 KB Output is correct
9 Correct 675 ms 16372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 18 ms 8372 KB Output is correct
13 Correct 15 ms 8212 KB Output is correct
14 Correct 16 ms 8368 KB Output is correct
15 Correct 46 ms 9936 KB Output is correct
16 Correct 113 ms 11356 KB Output is correct
17 Correct 138 ms 13656 KB Output is correct
18 Correct 694 ms 16372 KB Output is correct
19 Execution timed out 1567 ms 250732 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 16 ms 8284 KB Output is correct
4 Correct 13 ms 8284 KB Output is correct
5 Correct 18 ms 8356 KB Output is correct
6 Correct 45 ms 9820 KB Output is correct
7 Correct 111 ms 11516 KB Output is correct
8 Correct 130 ms 13660 KB Output is correct
9 Correct 675 ms 16372 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 15 ms 8284 KB Output is correct
13 Correct 15 ms 8284 KB Output is correct
14 Correct 16 ms 8364 KB Output is correct
15 Correct 45 ms 9724 KB Output is correct
16 Correct 120 ms 11584 KB Output is correct
17 Correct 156 ms 13668 KB Output is correct
18 Correct 677 ms 16464 KB Output is correct
19 Execution timed out 1558 ms 6092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1527 ms 4560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1546 ms 4308 KB Time limit exceeded
3 Halted 0 ms 0 KB -