Submission #782344

#	Time	Username	Problem	Language	Result	Execution time	Memory
782344		Ozy	Parking (CEOI22_parking)	C++17	10 / 100	64 ms	24128 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000

lli n,m,b,t;
lli estacionamiento[(MAX*2)+2][2], ya[MAX+2];
vector<lli> activos[MAX+2][2];
vector<lli> down,up,vacios;
vector<pll> res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    rep(i,1,m) {
        cin >> estacionamiento[i][0] >> estacionamiento[i][1];
        if (estacionamiento[i][1] != 0) {
            if(estacionamiento[i][1] == estacionamiento[i][0]) continue;

            up.push_back(i);
            activos[estacionamiento[i][1]][1].push_back(i);
            continue;
        }
        if (estacionamiento[i][0] != 0) {
            down.push_back(i);
            activos[estacionamiento[i][0]][0].push_back(i);
            continue;
        }
        vacios.push_back(i);
    }

    rep(i,1,n) {
        if (activos[i][1].size() < 2) continue;
        lli a = vacios[ vacios.size()-1 ];
        vacios.pop_back();

        res.push_back({activos[i][1][0],a});
        res.push_back({activos[i][1][1],a});
        ya[estacionamiento[ activos[i][1][1] ][1]] = 1;

        //acitva los menores
        a = estacionamiento[ activos[i][1][1] ][0];
        lli b = estacionamiento[ activos[i][1][0] ][0];

        activos[a][0].push_back(activos[i][1][1]);
        activos[b][0].push_back(activos[i][1][0]);

        activos[i][1].clear();
    }

    for(auto u : up) {
        lli val = estacionamiento[u][1];
        if (ya[val]) continue;
        if(activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) {

            res.push_back({activos[val][1][0], activos[val][0][0]});
            ya[val] = 1;

            //activa el de abajo
            val = estacionamiento[u][0];
            if (ya[val] == 1) continue;
            activos[val][0].push_back(u);

            while (activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) {
                res.push_back({activos[val][1][0], activos[val][0][0]});
                ya[val] = 1;

                //activa el de abajo
                lli x = activos[val][1][0];
                val = estacionamiento[ x ][0];
                if (ya[val] == 1) break;
                activos[val][0].push_back(x);
            }

        }
    }

    //checa por si quedo algun grande
    for(auto u : up) {
        lli val = estacionamiento[u][1];
        if (ya[val]) continue;

        lli v = vacios[vacios.size()-1];
        vacios.pop_back();

        res.push_back({activos[val][1][0], v});
        activos[val][0].push_back(v);

        //activa el de abajo
        val = estacionamiento[u][0];
        if (ya[val] == 1) continue;
        activos[val][0].push_back(u);

        while (activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) {
            res.push_back({activos[val][1][0], activos[val][0][0]});
            ya[val] = 1;

            //activa el de abajo
            lli x = activos[val][1][0];
            val = estacionamiento[ x ][0];
            if (ya[val] == 1) break;
            activos[val][0].push_back(x);
        }

    }

    rep(i,1,n) {
        //debugsl(i);
        //debug(activos[i][0].size());
        if(activos[i][0].size() == 2) {

            res.push_back({activos[i][0][0], activos[i][0][1]});

        }
    }

    cout << res.size() << "\n";
    for(auto r : res) cout << r.first << ' ' << r.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