Submission #1360732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360732		biserailieva	Circle Passing (EGOI24_circlepassing)	C++20	34 / 100	75 ms	1824 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(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;
}

• Subtask 1: 14 / 14
• Subtask 2: 20 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27