제출 #1360752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360752		biserailieva	Circle Passing (EGOI24_circlepassing)	C++20	14 / 100	520 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m, q;
    cin>>n>>m>>q;
    int A[m];
    bool prv=true;
    bool nula=true;
    if(m!=1)
    {
        prv=false;
    }
    for(int i=0;i<m;i++)
    {
        cin>>A[i];
    }
    int x[q], y[q];
    for(int i=0;i<q;i++)
    {
        cin>>x[i]>>y[i];
        if(x[i]!=A[0])
        {
            prv=false;
        }
        if(x[i]!=0)
        {
            nula=false;
        }
    }
    if(prv)
    {
        for(int i=0;i<q;i++)
        {
            int r1, r2, r3;
            r1=abs(x[i]-y[i]);
            r2=2*n-abs(x[i]-y[i]);
            if(x[i]<n)
            {
                x[i]+=n;
            }
            else
            {
                x[i]-=n;
            }
            r3=min(abs(x[i]-y[i]), 2*n-abs(x[i]-y[i]))+1;
            cout<<min({r1, r2, r3})<<endl;
        }
    }
    else if(nula)
    {
        vector<int>dist(n, -1);
        vector<bool>bff(n, false);
        for(int i=0;i<m;i++)
        {
            bff[A[i]]=true;
            if(A[i]<n)
            {
                bff[A[i]+n]=true;
            }
            else
            {
                bff[A[i]-n]=true;
            }
        }
        queue<int>qu;
        qu.push(0);
        dist[0]=0;
        while(!qu.empty())
        {
            int node=qu.front();
            qu.pop();
            vector<int>next;
            if(node==0)
            {
                next.push_back(2*n-1);
                next.push_back(1);
            }
            else if(node==2*n-1)
            {
                next.push_back(0);
                next.push_back(2*n-2);
            }
            else
            {
                next.push_back(node-1);
                next.push_back(node+1);
            }
            if(bff[node] && node<n)
            {
                next.push_back(node+n);
            }
            else if(bff[node-n] && node>=n)
            {
                next.push_back(node-n);
            }
            for(auto nxt : next)
            {
                if(dist[nxt%n]==-1)
                {
                    dist[nxt%n]=dist[node%n]+1;
                    qu.push(nxt);
                }
            }
        }
        for(int i=0;i<q;i++)
        {
            cout<<dist[y[i]%n]<<endl;
        }
    }
    else if(n<=1000 && m<=1000 && q<=1000)
    {
        for(int br=0;br<q;br++)
        {
            vector<int>G[2020];
            for(int i=0;i<2*n;i++)
            {
                if(i==2*n-1)
                {
                    G[i].push_back(0);
                    G[0].push_back(i);
                }
                else
                {
                    G[i].push_back(i+1);
                    G[i+1].push_back(i);
                }
            }
            for(int i=0;i<m;i++)
            {
                if(A[i]<n)
                {
                    G[A[i]].push_back(A[i]+n);
                    G[A[i]+n].push_back(A[i]);
                }
                else
                {
                    G[A[i]].push_back(A[i]-n);
                    G[A[i]-n].push_back(A[i]);
                }
            }
            int dist[2020];
            memset(dist, -1, sizeof(dist));
            queue<int>qu;
            qu.push(x[br]);
            dist[x[br]]=0;
            while(!qu.empty())
            {
                int node=qu.front();
                qu.pop();
                for(auto next : G[node])
                {
                    if(dist[next]==-1)
                    {
                        dist[next]=dist[node]+1;
                        qu.push(next);
                    }
                }
            }
            cout<<dist[y[br]]<<endl;
        }
    }
    return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 0 / 20
• 서브태스크 3: 0 / 22
• 서브태스크 4: 0 / 17
• 서브태스크 5: 0 / 27