oj.uz

Submission #817583

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

priority_queue<array<int, 3>> pq;


void 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++;

    pq.push({ret, b, t});

    // 0 , 1 , 2
    // return ret;
}

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;

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

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

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

    //

    int tmp;

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

            if (tops[i].second != -1)
            {
                value(tops[i].second, i);
                // pq.push({tmp, tops[i].second, i});
            }
        }
    }

    // empty, done

    while (!pq.empty() && empty_spaces > 0 && done != N)
    {
        array<int, 3> tmp1 = pq.top();
        pq.pop();

        int b = tmp1[1], t = tmp1[2];

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

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:180:9: warning: unused variable 'tmp' [-Wunused-variable]
  180 |     int tmp;
      |         ^~~

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 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Correct 1 ms 212 KB Output is correct
7 Partially correct 0 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 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 23 ms 2572 KB Output is partially correct
2 Partially correct 28 ms 3044 KB Output is partially correct
3 Partially correct 22 ms 2124 KB Output is partially correct
4 Partially correct 28 ms 1944 KB Output is partially correct
5 Partially correct 30 ms 3008 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 324 KB Output is correct
3 Partially correct 1 ms 340 KB Output is partially correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 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 212 KB Output is partially correct
5 Partially correct 1 ms 212 KB Output is partially correct
6 Correct 1 ms 212 KB Output is correct
7 Partially correct 0 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct
11 Partially correct 23 ms 2572 KB Output is partially correct
12 Partially correct 28 ms 3044 KB Output is partially correct
13 Partially correct 22 ms 2124 KB Output is partially correct
14 Partially correct 28 ms 1944 KB Output is partially correct
15 Partially correct 30 ms 3008 KB Output is partially correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -