oj.uz

Submission #632109

# Submission time Handle Problem Language Result Execution time Memory
632109 2022-08-19T12:42:17 Z arayi Parking (CEOI22_parking) C++17
100 / 100
 435 ms 87412 KB 
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};

const int N = 5e5 + 20;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 128;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1)
            ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream &operator<<(ostream &c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template <class T>
void maxi(T &a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
    a = min(a, b);
}

int n, m;
vii az, ind[N], g[N], g1[N];
bool col[N];
int a[N][2], t[N];
vii tp[3];
vector<pir> pat;
vii gg[N], gg1[N];
priority_queue<pair<int, int>> q;
void dfs(int v, int x1)
{
    if (t[v] == 1)
        gg1[x1].ad(v), gg[v].ad(x1);
    for (auto p : g1[v])
        dfs(p, x1);
}
vii sm;
void dfs1(int v)
{
    bool bl = 0;
    for (auto p : g[v])
    {
        if(!col[p])
        {
            dfs1(p);
            bl = 1;
        }
    }
    if(!bl) sm.ad(v);
}
void han(int i1)
{
    if (col[i1])
        return;
    if (t[i1] == 3)
    {
        if (az.empty())
        {
            cout << -1 << endl;
            exit(0);
        }
        pat.ad(MP(ind[i1][0], az.back()));
        pat.ad(MP(ind[i1][1], az.back()));
        az.pop_back();
        col[i1] = 1;
        for (auto p : gg1[i1])
        {
            for (int i = 0; i < gg[p].size(); i++)
            {
                if (gg[p][i] == i1)
                {
                    swap(gg[p][i], gg[p].back());
                    gg[p].pop_back();
                    break;
                }
            }
            q.push(MP(-gg[p].size(), p));
        }
        for (auto p : g1[i1])
            han(p);
    }
    else if (t[i1] == 2)
    {
        col[i1] = 1;
        pat.ad(MP(ind[i1][1], ind[i1][0]));
        for (auto p : g1[i1])
            han(p);
    }
    else
    {
        if (gg[i1].empty())
        {
            sm.clear();
            dfs1(i1);
            if (sm[0] == i1)
            {
                pat.ad(MP(ind[i1][1], ind[i1][0]));
                az.ad(ind[i1][1]);
                col[i1] = 1;
            }
            else
                for(auto p : sm) han(p);
        }
    }
}

int main()
{
    fastio;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        ::a[i][0] = a, ::a[i][1] = b;
        if (a == 0)
            az.ad(i);
        else
            ind[a].ad(i), ind[b].ad(i);
        if (a == b)
            col[a] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (col[i])
            continue;
        int i1 = ind[i][0], i2 = ind[i][1];
        if (a[i1][0] == i && a[i2][0] == i)
        {
            if (a[i1][1])
                g[i].ad(a[i1][1]);
            if (a[i2][1])
                g[i].ad(a[i2][1]);
            tp[0].ad(i);
            t[i] = 1;
        }
        if (a[i1][1] == i && a[i2][0] == i)
            swap(ind[i][0], ind[i][1]), swap(i1, i2);
        if (a[i1][0] == i && a[i2][1] == i)
        {
            if (a[i1][1])
                g[i].ad(a[i1][1]);
            g1[i].ad(a[i2][0]);
            tp[1].ad(i);
            t[i] = 2;
        }
        if (a[i1][1] == i && a[i2][1] == i)
        {
            g1[i].ad(a[i1][0]);
            g1[i].ad(a[i2][0]);
            tp[2].ad(i);
            t[i] = 3;
        }
        /*cout << i << "-";
        for(auto p : g[i]) cout << p << " ";
        cout << endl;*/
    }
    for (auto p : tp[2])
        dfs(p, p);
    /*for(auto p : tp[0])
    {
        cout << p << "-";
        for(auto p1 : gg[p]) cout << p1 << " ";
        cout << endl;
    }
    for(auto p : tp[2])
    {
        cout << p << "-";
        for(auto p1 : gg1[p]) cout << p1 << " ";
        cout << endl;
    }*/
    for (auto p : tp[0])
        q.push(MP(-gg[p].size(), p));
    while (!q.empty())
    {
        auto p = q.top();
        q.pop();
        if (col[p.sc])
            continue;
        sm.clear();
        dfs1(p.sc);
        for (auto p1 : sm)
            han(p1);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!col[i] && t[i] == 3)
            han(i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!col[i] && t[i] == 2)
        {
            if (az.empty())
            {
                cout << -1 << endl;
                exit(0);
            }
            pat.ad(MP(ind[i][1], az.back()));
            ind[i][1] = az.back();
            han(g1[i][0]);
        }
    }
    cout << pat.size() << endl;
    for (auto p : pat)
        cout << p.fr << " " << p.sc << "\n";
    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

Compilation message

Main.cpp: In function 'void han(int)':
Main.cpp:124:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for (int i = 0; i < gg[p].size(); i++)
      |                             ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59004 KB Output is correct
2 Correct 30 ms 59012 KB Output is correct
3 Correct 28 ms 59008 KB Output is correct
4 Correct 36 ms 58996 KB Output is correct
5 Correct 28 ms 58964 KB Output is correct
6 Correct 29 ms 58972 KB Output is correct
7 Correct 31 ms 58964 KB Output is correct
8 Correct 29 ms 58980 KB Output is correct
9 Correct 31 ms 59036 KB Output is correct
10 Correct 29 ms 58964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 68896 KB Output is correct
2 Correct 132 ms 71232 KB Output is correct
3 Correct 98 ms 66716 KB Output is correct
4 Correct 109 ms 66064 KB Output is correct
5 Correct 138 ms 71044 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59056 KB Output is correct
2 Correct 29 ms 59024 KB Output is correct
3 Correct 29 ms 59048 KB Output is correct
4 Correct 30 ms 59180 KB Output is correct
5 Correct 35 ms 59180 KB Output is correct
6 Correct 30 ms 59168 KB Output is correct
7 Correct 30 ms 59192 KB Output is correct
8 Correct 30 ms 59136 KB Output is correct
9 Correct 33 ms 59084 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59056 KB Output is correct
2 Correct 29 ms 59024 KB Output is correct
3 Correct 29 ms 59048 KB Output is correct
4 Correct 30 ms 59180 KB Output is correct
5 Correct 35 ms 59180 KB Output is correct
6 Correct 30 ms 59168 KB Output is correct
7 Correct 30 ms 59192 KB Output is correct
8 Correct 30 ms 59136 KB Output is correct
9 Correct 33 ms 59084 KB Output is correct
10 Correct 342 ms 86656 KB Output is correct
11 Correct 97 ms 66980 KB Output is correct
12 Correct 195 ms 80544 KB Output is correct
13 Correct 257 ms 85012 KB Output is correct
14 Correct 216 ms 81852 KB Output is correct
15 Correct 228 ms 81096 KB Output is correct
16 Correct 360 ms 87012 KB Output is correct
17 Correct 199 ms 80632 KB Output is correct
18 Correct 339 ms 87412 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 59092 KB Output is correct
2 Correct 30 ms 59092 KB Output is correct
3 Correct 35 ms 59156 KB Output is correct
4 Correct 30 ms 59084 KB Output is correct
5 Correct 30 ms 59024 KB Output is correct
6 Correct 32 ms 59084 KB Output is correct
7 Correct 30 ms 59060 KB Output is correct
8 Correct 35 ms 59160 KB Output is correct
9 Correct 31 ms 59084 KB Output is correct
10 Correct 30 ms 59092 KB Output is correct
11 Correct 32 ms 59200 KB Output is correct
12 Correct 31 ms 59180 KB Output is correct
13 Correct 33 ms 59164 KB Output is correct
14 Correct 30 ms 59172 KB Output is correct
15 Correct 31 ms 59152 KB Output is correct
16 Correct 33 ms 59220 KB Output is correct
17 Correct 31 ms 59080 KB Output is correct
18 Correct 31 ms 59160 KB Output is correct
19 Correct 36 ms 59092 KB Output is correct
20 Correct 30 ms 59184 KB Output is correct
21 Correct 33 ms 59140 KB Output is correct
22 Correct 30 ms 59092 KB Output is correct
23 Correct 30 ms 59092 KB Output is correct
24 Correct 31 ms 59160 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59004 KB Output is correct
2 Correct 30 ms 59012 KB Output is correct
3 Correct 28 ms 59008 KB Output is correct
4 Correct 36 ms 58996 KB Output is correct
5 Correct 28 ms 58964 KB Output is correct
6 Correct 29 ms 58972 KB Output is correct
7 Correct 31 ms 58964 KB Output is correct
8 Correct 29 ms 58980 KB Output is correct
9 Correct 31 ms 59036 KB Output is correct
10 Correct 29 ms 58964 KB Output is correct
11 Correct 114 ms 68896 KB Output is correct
12 Correct 132 ms 71232 KB Output is correct
13 Correct 98 ms 66716 KB Output is correct
14 Correct 109 ms 66064 KB Output is correct
15 Correct 138 ms 71044 KB Output is correct
16 Correct 30 ms 59056 KB Output is correct
17 Correct 29 ms 59024 KB Output is correct
18 Correct 29 ms 59048 KB Output is correct
19 Correct 30 ms 59180 KB Output is correct
20 Correct 35 ms 59180 KB Output is correct
21 Correct 30 ms 59168 KB Output is correct
22 Correct 30 ms 59192 KB Output is correct
23 Correct 30 ms 59136 KB Output is correct
24 Correct 33 ms 59084 KB Output is correct
25 Correct 342 ms 86656 KB Output is correct
26 Correct 97 ms 66980 KB Output is correct
27 Correct 195 ms 80544 KB Output is correct
28 Correct 257 ms 85012 KB Output is correct
29 Correct 216 ms 81852 KB Output is correct
30 Correct 228 ms 81096 KB Output is correct
31 Correct 360 ms 87012 KB Output is correct
32 Correct 199 ms 80632 KB Output is correct
33 Correct 339 ms 87412 KB Output is correct
34 Correct 29 ms 59092 KB Output is correct
35 Correct 30 ms 59092 KB Output is correct
36 Correct 35 ms 59156 KB Output is correct
37 Correct 30 ms 59084 KB Output is correct
38 Correct 30 ms 59024 KB Output is correct
39 Correct 32 ms 59084 KB Output is correct
40 Correct 30 ms 59060 KB Output is correct
41 Correct 35 ms 59160 KB Output is correct
42 Correct 31 ms 59084 KB Output is correct
43 Correct 30 ms 59092 KB Output is correct
44 Correct 32 ms 59200 KB Output is correct
45 Correct 31 ms 59180 KB Output is correct
46 Correct 33 ms 59164 KB Output is correct
47 Correct 30 ms 59172 KB Output is correct
48 Correct 31 ms 59152 KB Output is correct
49 Correct 33 ms 59220 KB Output is correct
50 Correct 31 ms 59080 KB Output is correct
51 Correct 31 ms 59160 KB Output is correct
52 Correct 36 ms 59092 KB Output is correct
53 Correct 30 ms 59184 KB Output is correct
54 Correct 33 ms 59140 KB Output is correct
55 Correct 30 ms 59092 KB Output is correct
56 Correct 30 ms 59092 KB Output is correct
57 Correct 31 ms 59160 KB Output is correct
58 Correct 296 ms 83232 KB Output is correct
59 Correct 342 ms 86332 KB Output is correct
60 Correct 296 ms 80216 KB Output is correct
61 Correct 317 ms 84292 KB Output is correct
62 Correct 96 ms 67272 KB Output is correct
63 Correct 307 ms 84576 KB Output is correct
64 Correct 249 ms 81680 KB Output is correct
65 Correct 344 ms 85628 KB Output is correct
66 Correct 363 ms 86716 KB Output is correct
67 Correct 200 ms 80004 KB Output is correct
68 Correct 272 ms 85312 KB Output is correct
69 Correct 276 ms 84572 KB Output is correct
70 Correct 196 ms 80568 KB Output is correct
71 Correct 203 ms 81624 KB Output is correct
72 Correct 205 ms 81340 KB Output is correct
73 Correct 362 ms 86888 KB Output is correct
74 Correct 216 ms 81088 KB Output is correct
75 Correct 365 ms 86120 KB Output is correct
76 Correct 365 ms 86676 KB Output is correct
77 Correct 367 ms 85696 KB Output is correct
78 Correct 216 ms 81380 KB Output is correct
79 Correct 435 ms 85776 KB Output is correct
80 Correct 212 ms 80692 KB Output is correct
81 Correct 344 ms 86788 KB Output is correct