Submission #1237030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237030		MarwenElarbi	Parking (CEOI22_parking)	C++20	50 / 100	312 ms	31596 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 2e5+5;
int place[nax][2];
int park[nax][2];
int outdeg[nax];
vector<int> dag[nax];
vector<int> adj[nax];
set<int> fre;
bool vis[nax];
int cycle[nax];
vector<int> cur,concur;
bool test=false;
vector<pair<int,int>> ans;
vector<int> topo;
void deplace(int x,int y){
    ans.push_back({x,y});
    int topx = 1 - (park[x][0] == 0) - (park[x][1] == 0); 
    int topy = 1 - (park[y][0] == 0) - (park[y][1] == 0);
    int vx = park[x][topx];
    park[y][topy+1] = vx;
    int indx=0;
    if(place[vx][1] == x) indx=1; 
    place[vx][indx]=y;
    park[x][topx] = 0;
    if(topx == 0) fre.insert(x);
    if(topy==-1){
        if (indx == 1) swap(place[vx][0] , place[vx][1]);
        fre.erase(y);
    }
}
void dfs(int x){
    if (cycle[x]==2) return;
    if(cycle[x]==1){
        test=true;
        return;
    }
    cycle[x]=1;
    for(auto u : dag[x]){
        dfs(u);
    }
    cycle[x]=2;
    cur.push_back(x);
}
void dfs1(int x){
    vis[x]=true;
    concur.push_back(x);
    for(auto u : adj[x]){
        if(!vis[u]) dfs1(u);
    }
}
void run_case(){
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) place[i][0]=place[i][1]=-1;
    for (int i = 1; i <= m; ++i)
    {
        cin>>park[i][0]>>park[i][1];
        if(park[i][0]+park[i][1]==0) fre.insert(i);
        if(park[i][0]==park[i][1]) continue;
        if(place[park[i][0]][0] == -1) place[park[i][0]][0] = i;
        else place[park[i][0]][1] = i;
        if(park[i][1] != 0){
            if(place[park[i][1]][1] == -1) place[park[i][1]][1] = i;
            else place[park[i][1]][0] = i; 
            //cout <<park[i][1]<<" "<< place[park[i][1]][0] <<" "<< place[park[i][1]][0]<< endl;
        }
        dag[park[i][1]].push_back(park[i][0]);
        outdeg[park[i][1]]++;
        adj[park[i][1]].push_back(park[i][0]);
        adj[park[i][0]].push_back(park[i][1]);
    }
    //cout << place[1][0] << " "<<place[1][1]<<endl;
    for (int i = 1; i <= n; ++i)
    {
        if(place[i][0]==place[i][1]) continue;
        if(!vis[i]){
            test=false;
            cur.clear();
            concur.clear();
            dfs1(i);
            for(auto u : concur) dfs(u);
            if(test){
                if(fre.empty()){
                    cout << -1 << endl;
                    return;
                }else{
                    reverse(cur.begin(),cur.end());
                    int cnt = *fre.begin();
                    int lst=cnt;
                    for(auto u : cur){
                        int temp = place[u][1];
                        deplace(place[u][1] , lst);
                        lst = temp;
                    }
                    deplace(lst , cnt);
                }
            }else{
                for(auto u : cur) topo.push_back(u);
            }
        }
    }
    reverse(topo.begin(),topo.end());
    for(auto u : topo){
        if(outdeg[u] == 2){
            if(fre.empty()){
                cout << -1 <<endl;
                return;
            }
            int pivot = *fre.begin();
            int y = place[u][1];
            deplace(place[u][0] , pivot);
            deplace(y , pivot);
        }else if(outdeg[u] == 1){
            deplace(place[u][1] , place[u][0]);
        }else if(outdeg[u] == 0){
            deplace(place[u][1] , place[u][0]);
        }
    }
    cout << ans.size() << endl;
    for (auto u : ans)
    {
        cout << u.fi << " " << u.se << endl;
    }
}
int main() {
    run_case();
}

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