oj.uz

Submission #817510

# Submission time Handle Problem Language Result Execution time Memory
817510 2023-08-09T13:04:54 Z Ellinor Parking (CEOI22_parking) C++14
4 / 100
 29 ms 1948 KB 
#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;

//

vector<pii> ans;

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;

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

            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";

    //

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

    // cerr << "lonely_bottom : ";
    // rep(i,0,N)
    // {
    //     cerr << lonely_bottom[i] << " ";
    // }

    // cerr << "tops : \n";
    // rep(i,0,N)
    // {
    //     cerr << tops[i].first << " " << tops[i].second << "\n";
    // }

    // cerr << "bottoms : \n";
    // rep(i,0,N)
    // {
    //     cerr << bottoms[i].first << " " << bottoms[i].second << "\n";
    // }
}

Subtask #1
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 0 ms 212 KB Output is partially correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 0 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Correct 0 ms 212 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 20 ms 1568 KB Output is partially correct
2 Partially correct 29 ms 1860 KB Output is partially correct
3 Partially correct 23 ms 1236 KB Output is partially correct
4 Partially correct 18 ms 1168 KB Output is partially correct
5 Partially correct 29 ms 1948 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 0 ms 340 KB Output is correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 0 ms 212 KB Output is partially correct
5 Correct 1 ms 212 KB Output is correct
6 Partially correct 0 ms 340 KB Output is partially correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 0 ms 212 KB Output is partially correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 0 ms 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Correct 0 ms 212 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct
11 Partially correct 20 ms 1568 KB Output is partially correct
12 Partially correct 29 ms 1860 KB Output is partially correct
13 Partially correct 23 ms 1236 KB Output is partially correct
14 Partially correct 18 ms 1168 KB Output is partially correct
15 Partially correct 29 ms 1948 KB Output is partially correct
16 Incorrect 0 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -