제출 #817470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817470		Ellinor	Parking (CEOI22_parking)	C++14	4 / 100	25 ms	3376 KiB

Main

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

#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

// #include <iostream>
// #include <vector>
// #include <queue>
// #include <string>
// #include <cmath>
// #include <cstdlib>
// #include <set>
// #include <iomanip>
// #include <limits>
// #include <map>
// #include <assert.h>
// #include <algorithm>
// #include <list>
// #include <iterator>
// #include <fstream>
// #include <random>
// #include <unordered_map>
// using namespace std;

// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

// typedef long long ll;
// #define rep(i, a, b) for (int i = (a); i < int(b); i++)
// typedef pair<ll, ll> pll;
// typedef pair<int, int> pii;
// #define pb push_back

// inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

// ll INF = 1000000000;
// ll mod = 1e9 + 7;

//

int moves = 0;
int done = 0;

int N, M;

int empty_spaces;
vector<bool> lonely_bottom;
vector<pii> bottoms;
vector<pii> tops;


void new_space(int b, int t)
{
    if (b == -1) {
        empty_spaces++;
        return;
    }

    if (t == -1) {
        if (lonely_bottom[b] == true) {
            // lonely_bottom[b] = false;
            // tops[b].first = -1; // b;
            // bottoms[b].first = -1; // b;
            moves++;
            done++;
            empty_spaces++;
            return;
        }

        if (tops[b].first != -1) {
            int tmp = tops[b].first;

            tops[b].first = -1; // b
            // bottoms[b].first = -1; // b;
            moves++;
            done++;

            new_space(tmp, -1);
            return;
        }

        lonely_bottom[b] = true;
        return;
    }

    if (lonely_bottom[t] == true)
    {
        // lonely_bottom[t] = false;
        // bottoms[t].first = -1; // t;
        // tops[t].first = -1; // t;
        moves++;
        done++;

        new_space(b, -1);
        return;
    }

    if (b == t) {
        done++;
        return; //
    }

    if (tops[t].first != -1) tops[t].second = b;
    else tops[t].first = b;

    if (bottoms[b].first != -1) bottoms[b].second = t;
    else bottoms[b].first = t;
}

int value(int b, int t)
{
    //
    assert (b != t);
    assert (lonely_bottom[t] == false);

    int ret = 0;
    
    if (tops[t].second != -1) ret++;

    if (lonely_bottom[b]) ret++;
    if (tops[b].first != -1) ret++;

    // 0 , 1 , 2
    return ret;
}

int32_t main()
{
    fast();
    cin >> N >> M;
    empty_spaces = 0;
    lonely_bottom.assign(N, false);
    bottoms.assign(N, {-1, -1});
    tops.assign(N, {-1, -1});

    int b, t;
    rep(i,0,M)
    {
        cin >> b >> t;
        b--; t--;
        new_space(b, t);
    }

    // cerr << moves << " " << done << " " << empty_spaces << "\n";

    //

    queue<pii> q0, q1, q2;
    int tmp;

    rep(i,0,N)
    {
        if (tops[i].first != -1)
        {
            tmp = value(tops[i].first, i);
            if (tmp == 0) q0.push({tops[i].first, i});
            else if (tmp == 1) q1.push({tops[i].first, i});
            else q2.push({tops[i].first, i}); // == 2

            if (tops[i].second != -1)
            {
                tmp = value(tops[i].second, i);
                if (tmp == 0) q0.push({tops[i].second, i});
                else if (tmp == 1) q1.push({tops[i].second, i});
                else q2.push({tops[i].second, i}); // == 2
            }
        }
    }

    // empty, done

    while (!q2.empty() && empty_spaces > 0 && done != N)
    {
        pii tmp1 = q2.front();
        q2.pop();

        int b = tmp1.first, t = tmp1.second;

        if (!(tops[t].first == b || tops[t].second == b)) continue;
        // val
        
        int other;
        if (tops[t].first != b) other = tops[t].first;
        if (tops[t].second != b) other = tops[t].second; // -1
        tops[t] = {other, -1};

        if (bottoms[b].first != t) other = bottoms[b].first;
        if (bottoms[b].second != t) other = bottoms[b].second; // -1
        bottoms[b] = {other, -1};

        moves++;
        empty_spaces--;
        new_space(b, -1);
        new_space(t, -1); // ?
    }

    while (!q1.empty() && empty_spaces > 0 && done != N)
    {
        pii tmp1 = q1.front();
        q1.pop();

        int b = tmp1.first, t = tmp1.second;

        if (!(tops[t].first == b || tops[t].second == b)) continue;
        // val
        
        int other;
        if (tops[t].first != b) other = tops[t].first;
        if (tops[t].second != b) other = tops[t].second; // -1
        tops[t] = {other, -1};

        if (bottoms[b].first != t) other = bottoms[b].first;
        if (bottoms[b].second != t) other = bottoms[b].second; // -1
        bottoms[b] = {other, -1};

        moves++;
        empty_spaces--;
        new_space(b, -1);
        new_space(t, -1); // ?
    }

    while (!q0.empty() && empty_spaces > 0 && done != N)
    {
        pii tmp1 = q0.front();
        q0.pop();

        int b = tmp1.first, t = tmp1.second;

        if (!(tops[t].first == b || tops[t].second == b)) continue;
        // val
        
        int other;
        if (tops[t].first != b) other = tops[t].first;
        if (tops[t].second != b) other = tops[t].second; // -1
        tops[t] = {other, -1};

        if (bottoms[b].first != t) other = bottoms[b].first;
        if (bottoms[b].second != t) other = bottoms[b].second; // -1
        bottoms[b] = {other, -1};

        moves++;
        empty_spaces--;
        new_space(b, -1);
        new_space(t, -1); // ?
    }

    if (done == N)
    {
        cout << moves << "\n";
        //
    }
    else cout << -1 << "\n";
}

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