제출 #1310400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310400		mpawicka_77	Parking (CEOI22_parking)	C++20	20 / 100	110 ms	139092 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3;
vector<int>parking[N];
vector<int>gdzie[N];
set<int>puste;
vector<pair<int,int>>res;
bool zle=false;
void przeloz(int a,int b)
{
    res.push_back({a,b});
    if(parking[b].size()==0)puste.erase(b);
    int col=parking[a].back();
    parking[b].push_back(col);
    parking[a].pop_back();

    if(gdzie[col][0]==a)gdzie[col][0]=b;
    else gdzie[col][1]=b;

    if(parking[a].size()==0)puste.insert(a);
}
void jedynki(int nr_parkingu)
{
    if(parking[nr_parkingu].size()!=1)return;
    int col=parking[nr_parkingu][0];
    int nr2=gdzie[col][0];
    if(nr2==nr_parkingu)nr2=gdzie[col][1];
    if(parking[nr2].back()==col)
    {
        przeloz(nr2, nr_parkingu);
        if(parking[nr2].size()==1)
        {
            jedynki(nr2);
        }
    }
    else
    {
        int x=col, nr1=nr_parkingu;
        while(true)
        {
            int nr2=gdzie[x][0];
            if(nr2==nr1)nr2=gdzie[x][1];

            if(parking[nr2].back()==x)
            {
                if(puste.empty())
                {
                    zle=true;
                    break;
                }
                int miejsce=(*puste.begin());
                przeloz(nr1, miejsce);
                przeloz(nr2, miejsce);
                jedynki(nr1);
                jedynki(nr2);
                break;
            }
            else
            {
                x=parking[nr2].back();
                nr1=nr2;
            }
        }
    }
}
int ost=0;
void park1(int nr_parkingu)
{
    if(parking[nr_parkingu].size()!=1)return;
    int col=parking[nr_parkingu][0];
    int nr2=gdzie[col][0];
    if(nr2==nr_parkingu)nr2=gdzie[col][1];

    if(parking[nr2].back()==col)
    {
        przeloz(nr2, nr_parkingu);
        if(parking[nr2].size()==1)
        {
            park1(nr2);
        }
    }
    else
    {
         ost=nr_parkingu;
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin>>n >> m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        if(a!=0)
        {
            parking[i].push_back(a);
            gdzie[a].push_back(i);
        }
        if(b!=0)
        {
            parking[i].push_back(b);
            gdzie[b].push_back(i);
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(parking[i].size()==0)
        {
            puste.insert(i);
        }
    }
    for(int i=1; i<=m; i++)
    {
        if(parking[i].size()==1)park1(i);
    }
    for(int i=1; i<=m; i++)
    {
        if(parking[i].size()==1)
        {
            jedynki(i);
        }
    }
    if(zle)
    {
        cout<<"-1\n";
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        int nr1=gdzie[i][0], nr2=gdzie[i][1];
        if(nr1==nr2)continue;
        if(parking[nr1].back()==i&&parking[nr2].back()==i)
        {
            if(puste.size()==0)
            {
                cout<<"-1\n";
                return 0;
            }
            int miejsce=*puste.begin();
            przeloz(nr1, miejsce);
            przeloz(nr2, miejsce);
            park1(nr1);
            nr1=ost;
            park1(nr2);
            nr2=ost;
            jedynki(nr1);
            jedynki(nr2);
        }
        if(zle)
        {
            cout<<"-1\n";
            return 0;
        }
    }
    for(int i=1; i<=n; i++)
    {
        int nr1=gdzie[i][0], nr2=gdzie[i][1];
        if(nr1==nr2)continue;
        if(puste.size()==0)
        {
            cout<<"-1\n";
            return 0;
        }
        int miejsce=*puste.begin();
        przeloz(nr1, miejsce);
        park1(nr1);
        park1(miejsce);
    }
    cout<<res.size()<<"\n";
    return 0;
}

• Subtask 1: 2 / 10
• Subtask 2: 2 / 10
• Subtask 3: 5 / 25
• Subtask 4: 3 / 15
• Subtask 5: 5 / 25
• Subtask 6: 3 / 15