oj.uz

Submission #817470

# Submission time Handle Problem Language Result Execution time Memory
817470 2023-08-09T12:47:12 Z Ellinor Parking (CEOI22_parking) C++14
4 / 100
 25 ms 3376 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;

//

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 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 1 ms 340 KB Output is partially correct
5 Partially correct 0 ms 212 KB Output is partially correct
6 Correct 0 ms 296 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 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 22 ms 2952 KB Output is partially correct
2 Partially correct 23 ms 3376 KB Output is partially correct
3 Partially correct 19 ms 2428 KB Output is partially correct
4 Partially correct 19 ms 2312 KB Output is partially correct
5 Partially correct 25 ms 3352 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 1 ms 340 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 340 KB Output is partially correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 KB Output is partially correct
4 Partially correct 1 ms 324 KB Output is partially correct
5 Correct 1 ms 340 KB Output is correct
6 Partially correct 1 ms 340 KB Output is partially correct
7 Correct 1 ms 464 KB Output is correct
8 Incorrect 1 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 1 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 1 ms 340 KB Output is partially correct
5 Partially correct 0 ms 212 KB Output is partially correct
6 Correct 0 ms 296 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct
11 Partially correct 22 ms 2952 KB Output is partially correct
12 Partially correct 23 ms 3376 KB Output is partially correct
13 Partially correct 19 ms 2428 KB Output is partially correct
14 Partially correct 19 ms 2312 KB Output is partially correct
15 Partially correct 25 ms 3352 KB Output is partially correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -