Submission #1231497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231497		alexander707070	Parking (CEOI22_parking)	C++20	10 / 100	1104 ms	10688 KiB

Main

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

int n,m,a,b,cnt;
vector<int> v[MAXN],open;
int in[MAXN],br[MAXN],to[MAXN],cycles;
bool ok[MAXN],vis[MAXN];

pair<int,int> pos[MAXN];
vector< pair<int,int> > sol;

void endt(){
    cout<<"-1\n";
    exit(0);
}

void dfs(int x){
    vis[x]=true;

    if(!vis[to[x]]){
        sol.push_back({pos[x].second,pos[x].first});
        dfs(to[x]);
    }
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;

        if(a==0 and b==0)open.push_back(i);

        if(a!=0 and b!=0 and a!=b){
            v[b].push_back(a);
            in[a]++;
        }

        if(pos[a].first==0)pos[a].first=i;
        else pos[a].second=i;

        if(pos[b].second==0)pos[b].second=i;
        else pos[b].first=i;

        br[a]++;
        br[b]+=2;

        if(a==b and a!=0)ok[a]=true;
    }

    while(true){

        int best=0,fine=0;
        bool done=false;

        for(int i=1;i<=n;i++){
            if(ok[i])continue;

            if(in[i]==0){
                if(br[i]<=3){

                    if(br[i]==2)open.push_back(pos[i].second);
                    sol.push_back({pos[i].second,pos[i].first});

                    ok[i]=true; done=true;
                
                    if(!v[i].empty())in[v[i][0]]--;
                }else{
                    if(in[v[i][0]]==1 or in[v[i][1]]==1){
                        best=i;
                    }else fine=i;
                }
            }
        }

        if(best!=0){
            
            if(open.empty())endt();
            in[v[best][0]]--;
            in[v[best][1]]--;
            ok[best]=true;

            sol.push_back({pos[best].first,open.back()});
            sol.push_back({pos[best].second,open.back()});
            open.pop_back();
            
        }else if(fine!=0){

            if(open.empty())endt();
            in[v[fine][0]]--;
            in[v[fine][1]]--;
            ok[fine]=true;

            sol.push_back({pos[fine].first,open.back()});
            sol.push_back({pos[fine].second,open.back()});
            open.pop_back();

        }else if(!done)break;
    }

    for(int i=1;i<=n;i++){
        if(!ok[i] and open.empty())endt();

        if(!ok[i])to[i]=v[i][0];
    }

    for(int i=1;i<=n;i++){
        if(to[i]!=0){
            sol.push_back({pos[i].second,open.back()});
            
            dfs(i);
            sol.push_back({pos[i].first,open.back()});
            open.pop_back();
            open.push_back(pos[i].first);
        }
    }

    cout<<sol.size()<<"\n";
    for(auto s:sol){
        cout<<s.first<<" "<<s.second<<"\n";
    }

    return 0;
}

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