Submission #1236582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236582		YassineBenYounes	Parking (CEOI22_parking)	C++20	12 / 100	246 ms	41732 KiB

Main

#include<bits/stdc++.h>
#include<chrono>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

////////////////////Only Clear Code//////////////////////////
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("outputs.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
const int mx = 2e5+5;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 998244353;
const int sq = 300;

int arr[mx][2];
int n, m;
vi graph[mx], congraph[mx], rgraph[mx];
vi cur;
int state[mx];
bool cycle = 0;
vii res;
set<int> fre;
int place[mx][2];
bool vis[mx];
vi curcon;
/*
    invariant:
    in array place
    bottom is always in indice 0
*/

// develop the function more

void deplace(int x, int y){
    // x to y
    res.pb({x, y});
    /*
    top:
    -1 -----> empty
    1 -----> full
    0 -----> half full
    */
    int topx = 1 - (arr[x][0] == 0) - (arr[x][1] == 0);
    int topy = 1 - (arr[y][0] == 0) - (arr[y][1] == 0);
    assert(topx != -1 && topy != 1);
    int vx = arr[x][topx];
    int indx = 0;
    if(place[vx][1] == x)indx = 1;
    arr[x][topx] = 0;
    arr[y][topy+1] = vx;
    if(topx == 0)fre.insert(x);
    place[vx][indx] = y;
    if(topy == -1){
        // y is empty
        if(indx == 1)swap(place[vx][0], place[vx][1]);
        assert(fre.count(y));
        fre.erase(y);
    }
    else if(topy == 0){
        // contains an element
        assert(arr[y][0] == vx);
    }
    /*cout << x << " ************ " << y << endl;
    for(int i = 0; i < m;i++){
        cout << arr[i][0] << " " << arr[i][1] << endl;
    }*/
}

void dfs1(int node){
    if(vis[node])return;
    curcon.pb(node);
    vis[node] = 1;
    for(int adj : congraph[node]){
        dfs1(adj);
    }
}

void dfs(int node){
    if(state[node] == 2)return;
    if(state[node] == 1){
        cycle = 1;
        return;
    }
    state[node] = 1;
    for(int adj : graph[node]){
        dfs(adj);
    }
    state[node] = 2;
    cur.pb(node);
}

// DONT FORGET THAT DEPLACE UPDATES EVERYTHING

// might tle

void rassembler(int i){
    int a = place[i][0], b = place[i][1];
    if(a == b)return;
    if(arr[a][1] == 0 && arr[b][1] == i){
        deplace(b, a);
        rassembler(arr[b][0]);
    }
    if(arr[a][1] == 0 && arr[b][1] == 0){
        deplace(b, a);
    }
}

int marked[mx];

void rdfs(int node){
    if(marked[node]!=0)return;
    if(graph[node].size() == 2)marked[node] = 1;
    else{
        marked[node] = -1;
    }
    for(int adj : rgraph[node]){
        rdfs(adj);
    }
}
/*
bool compare(const vi &a, const vi &b){
    int cnta = 0;
    for(int x : a){
        if(graph[x].size() == 0 && rgraph[x].size() == 1)rdfs(x);
    }
    for(int x : a){
        if(graph[x].size() == 2 && !marked[x])cnta++;
    }
    int cntb = 0;
    for(int x : b){
        if(graph[x].size() == 0 && rgraph[x].size() == 1)rdfs(x);
    }
    for(int x : b){
        if(graph[x].size() == 2 && (marked[x] == 0 || marked[x] == -1))cntb++;
    }
    for(int x : a){
        marked[x] = 0;
    }
    for(int x : b){
        marked[x] = 0;
    }
    return max(1, cnta) < max(1, cntb);
}*/

bool compare(const vi &a, const vi &b){
    int cnta = 0;
    for(int x : a){
        if(graph[x].size() == 2)cnta++;
    }
    int cntb = 0;
    for(int x : a){
        if(graph[x].size() == 2)cntb++;
    }
    return cnta < cntb;
}

void run_case(){
    cin >> n >> m;
    for(int i = 1; i <= n;i++){
        place[i][0] = place[i][1] = -1;
    }
    for(int i = 0; i < m;i++){
        cin >> arr[i][0] >> arr[i][1];
        if(arr[i][0]+arr[i][1]==0){
            fre.insert(i);
        }
        if(arr[i][0] == arr[i][1]){
            continue;
        }
        if(place[arr[i][0]][0] == -1){
            place[arr[i][0]][0] = i;
        }
        else{
            place[arr[i][0]][1] = i;
        }
        if(arr[i][1] == 0)continue;
        if(place[arr[i][1]][1] == -1){
            place[arr[i][1]][1] = i;
        }
        else{
            place[arr[i][1]][0] = i;
        }
    }
    // if i can form a pair instantly do it
    for(int i = 1; i <= n;i++){
        rassembler(i);
    }
    // form the graphs
    for(int i = 0; i < m;i++){
        if(arr[i][0]+arr[i][1]==0){
            fre.insert(i);
        }
        if(arr[i][0] == arr[i][1]){
            continue;
        }
        if(arr[i][1] == 0)continue;
        graph[arr[i][1]].pb(arr[i][0]);
        rgraph[arr[i][0]].pb(arr[i][1]);
        congraph[arr[i][1]].pb(arr[i][0]);
        congraph[arr[i][0]].pb(arr[i][1]);
    }
    //cout << 9999 << endl;
    vector<vi> cycles;
    vector<vi> components;
    // cycles need one extra space
    // modify it to visit all of the component before moving on to others
    for(int i = 1; i <= n;i++){
        if(place[i][0] == place[i][1])continue;
        if(!vis[i]){
            cur.clear();
            cycle = 0;
            curcon.clear();
            dfs1(i);
            for(int x : curcon){
                dfs(x);
            }
            if(cycle){
                // manoeuver the cycle
                reverse(all(cur));
                cycles.pb(cur);
            }
            else{
                reverse(all(cur));
                components.pb(cur);
            }
        }
    }
    //process all components in increasing 'difficulty'
    sort(all(components), compare);
    for(vi cur : components){
        /*cout << "GHHHHHH" << endl;
        for(int x : cur){
            cout << x << " ";
        }
        cout << endl;*/
        for(int x : cur){
            // process node x
            if(graph[x].size() == 2){
                // 2 outgoing edges
                if(fre.empty()){
                    cout << -1 << endl;
                    return;
                }
                int pivot = *fre.begin();
                int y = place[x][1];
                deplace(place[x][0], pivot);
                deplace(y, pivot);
            }
            else if(graph[x].size() == 1){
                // one outgoing edge
                deplace(place[x][1], place[x][0]);
            }
            else{
                // no outgoing edges
                deplace(place[x][1], place[x][0]);
            }
        }
    }
    //process all cycles
    for(vi cur : cycles){
        if(fre.empty()){
            cout << -1 << endl;
            return;
        }
        else{
            int pivot = *fre.begin();
            int st = pivot;
            for(int x : cur){
                int temp = place[x][1];
                deplace(place[x][1], pivot);
                pivot = temp;
            }
            deplace(pivot, st);
        }
    }
    // res
    cout << res.size() << endl;
    for(pii x : res){
        cout << x.ff << " " << x.ss << endl;
    }
}

int32_t main(){
    speed;
    int t = 1;
    //cin >> t;
    while(t--){
        run_case();
    }
}
 
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message (stderr)

Main.cpp: In function 'void init()':
Main.cpp:29:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:31:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | freopen("outputs.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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