oj.uz

Submission #634465

# Submission time Handle Problem Language Result Execution time Memory
634465 2022-08-24T13:02:04 Z Markomafko972 Parking (CEOI22_parking) C++14
4 / 100
 111 ms 30924 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, m, a, b, e, kol, kolg, jed, sol;
vector<int> v[200005];
int g[200005];
int bio[200005];
vector<int> pr;
int gdje[200005][5];
vector<int> smj[200005];
int ideu[200005];
set< pair<int, pair<int, int> > > s;
set< pair<int, pair<int, int> > > :: iterator it;
pair<int, int> pos[200005];
vector< pair<int, int> > out;
vector< pair<int, int> > tren;
int sam[200005];
int znak[200005];
int dalje[200005];

vector< pair< int, pair<int, int> > > svi;
vector<int> pravi[200005];

void dfs(int x) {
    if (v[x].size() == 1) jed = 1;

    bio[x] = 1;
    kol++;
    if (g[x] == 2) {
        kolg++;
        s.insert({0, {1, x}});
    }
    else {
        s.insert({ideu[x], {0, x}});
    }

    for (int i = 0; i < v[x].size(); i++) {
        if (bio[v[x][i]] == 0) dfs(v[x][i]);
    }
}

void rek(int x) {
    bio[x] = 1;
    if (gdje[pos[x].X][0] == x && gdje[pos[x].Y][0] == x) tren.push_back({x, 1});
    else if (gdje[pos[x].X][1] == x && gdje[pos[x].Y][1] == x) tren.push_back({x, -1});
    else tren.push_back({x, 0});

    for (int i = 0; i < v[x].size(); i++) {
        if (bio[v[x][i]] == 0) rek(v[x][i]);
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) pos[i] = {-1, -1};

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        gdje[i][0] = a;
        gdje[i][1] = b;
        if (pos[a].X == -1) pos[a].X = i;
        else pos[a].Y = i;

        if (pos[b].X == -1) pos[b].X = i;
        else pos[b].Y = i;

        if (a == 0 && b == 0) {
            e++;
            pr.push_back(i);
        }
        else if (a != b && a > 0 && b > 0) {
            smj[a].push_back(b);
            ideu[a]++;
            v[a].push_back(b);
            v[b].push_back(a);
            g[b]++;
            pravi[b].push_back(a);
        }
        else if (b == 0) {
            if (sam[a] == 0) sam[a] = i+1;
            else {
                sol++;
                e++;
                out.push_back({i, sam[a]-1});
                pr.push_back(i);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (bio[i] == 0 && (int)v[i].size() > 0) {
            kol = 0, kolg = 0, jed = 0;
            s.clear();
            dfs(i);

            svi.push_back({1-jed, {kolg, i}});

            sol += kol+max(1, kolg);
        }
    }

    sort(svi.begin(), svi.end());
    memset(bio, 0, sizeof bio);
    for (int i = 0; i < svi.size(); i++) {
        if (svi[i].X == 0) {
            if (svi[i].Y.X > 0 && e < 1) {
                cout << -1;
                return 0;
            }

            if (svi[i].Y.X == 0) sol--;
            e++;
        }
        else {
            if ((svi[i].Y.X > 1 && e < 2) || e < 1) {
                cout << -1;
                return 0;
            }
        }

        tren.clear();
        rek(svi[i].Y.Y);
        int raz = 0;
        for (int j = 0; j < tren.size(); j++) {
            if (tren[j].Y != 0) raz++;
        }

        if (raz == 0 && svi[i].X == 1) {
            int wh = pos[svi[i].Y.Y].X;
            if (gdje[wh][0] != svi[i].Y.Y) wh = pos[svi[i].Y.Y].Y;

            out.push_back({wh, pr.back()});
            pravi[ smj[svi[i].Y.Y][0] ].clear();
            if (pos[ smj[svi[i].Y.Y][0] ].X == wh) pos[ smj[svi[i].Y.Y][0] ].X = pr.back();
            else pos[ smj[svi[i].Y.Y][0] ].Y = pr.back();
            smj[svi[i].Y.Y].clear();
        }
        
        s.clear();
        for (int j = 0; j < tren.size(); j++) {
        	znak[tren[j].X] = 1-tren[j].Y;
        	dalje[tren[j].X] = (int)smj[tren[j].X].size();
        	s.insert({(int)smj[tren[j].X].size(), {1-tren[j].Y, tren[j].X}});
		}

        for (int abc = 0; abc < tren.size(); abc++) {
            int novi = -1, w = 0;
			
			pair<int, pair<int, int> > broj = *s.begin();
            s.erase(s.begin());
        	novi = broj.Y.Y;
            w = 1 - broj.Y.X;
            	
            /*for (int j = 0; j < pravi[novi].size(); j++) {
            	int susjed = pravi[novi][j];
            	if (s.find({dalje[susjed], {znak[susjed], susjed}}) != s.end()) {
					s.erase({dalje[susjed], {znak[susjed], susjed}});
            		dalje[susjed]--;
            		s.insert({dalje[susjed], {znak[susjed], susjed}});
            	}
            	else {
            		while (1) {
            			
					}
				}
			}*/
			
            /*for (int j = 0; j < tren.size(); j++) {
                if (bio[tren[j].X] == 2) continue;
                int koll = 0, k2 = 0;
                if (smj[tren[j].X].size() > 0 && bio[smj[tren[j].X][0]] != 2) {
                    koll++;
                    if (g[smj[tren[j].X][0]] == 2) k2++;
                }
                if (smj[tren[j].X].size() > 1 && bio[smj[tren[j].X][1]] != 2) {
                    koll++;
                    if (g[smj[tren[j].X][1]] == 2) k2++;
                }

                if (koll == 0 && tren[j].Y >= 0 && k2 == 0) {
                    novi = tren[j].X;
                    w = tren[j].Y;
                    break;
                }

                if (koll == 0) {
                    novi = tren[j].X;
                    w = tren[j].Y;
                }
            }

            bio[novi] = 2;*/

            if (w == -1) {
                out.push_back({pos[novi].X, pr.back()});
                out.push_back({pos[novi].Y, pr.back()});
                pr.pop_back();
            }
            else if (w == 1) {
                out.push_back({pos[novi].X, pos[novi].Y});
                pr.push_back(pos[novi].X);
            }
            else {
                if (gdje[ pos[novi].X ][0] == novi) out.push_back({pos[novi].Y, pos[novi].X});
                else out.push_back({pos[novi].X, pos[novi].Y});
            }
        }
    }

    cout << sol << "\n";
    //for (int i = 0; i < out.size(); i++) cout << out[i].X+1 << " " << out[i].Y+1 << "\n";

    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int)':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < v[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void rek(int)':
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < v[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < svi.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (int j = 0; j < tren.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:146:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int j = 0; j < tren.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:152:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int abc = 0; abc < tren.size(); abc++) {
      |                           ~~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 15188 KB Output is partially correct
2 Partially correct 8 ms 15132 KB Output is partially correct
3 Partially correct 10 ms 15188 KB Output is partially correct
4 Partially correct 8 ms 15232 KB Output is partially correct
5 Partially correct 8 ms 15196 KB Output is partially correct
6 Correct 8 ms 15128 KB Output is correct
7 Partially correct 8 ms 15188 KB Output is partially correct
8 Correct 10 ms 15188 KB Output is correct
9 Correct 8 ms 15140 KB Output is correct
10 Partially correct 8 ms 15188 KB Output is partially correct

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 86 ms 26548 KB Output is partially correct
2 Partially correct 111 ms 28524 KB Output is partially correct
3 Partially correct 59 ms 24480 KB Output is partially correct
4 Partially correct 69 ms 23520 KB Output is partially correct
5 Partially correct 104 ms 28452 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 30844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 30844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 15360 KB Output is partially correct
2 Correct 9 ms 15444 KB Output is correct
3 Partially correct 9 ms 15284 KB Output is partially correct
4 Partially correct 8 ms 15316 KB Output is partially correct
5 Correct 8 ms 15188 KB Output is correct
6 Partially correct 9 ms 15316 KB Output is partially correct
7 Correct 8 ms 15316 KB Output is correct
8 Partially correct 9 ms 15316 KB Output is partially correct
9 Partially correct 10 ms 15316 KB Output is partially correct
10 Correct 11 ms 15280 KB Output is correct
11 Partially correct 9 ms 15400 KB Output is partially correct
12 Partially correct 8 ms 15316 KB Output is partially correct
13 Correct 8 ms 15316 KB Output is correct
14 Correct 9 ms 15316 KB Output is correct
15 Correct 8 ms 15316 KB Output is correct
16 Runtime error 26 ms 30924 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 15188 KB Output is partially correct
2 Partially correct 8 ms 15132 KB Output is partially correct
3 Partially correct 10 ms 15188 KB Output is partially correct
4 Partially correct 8 ms 15232 KB Output is partially correct
5 Partially correct 8 ms 15196 KB Output is partially correct
6 Correct 8 ms 15128 KB Output is correct
7 Partially correct 8 ms 15188 KB Output is partially correct
8 Correct 10 ms 15188 KB Output is correct
9 Correct 8 ms 15140 KB Output is correct
10 Partially correct 8 ms 15188 KB Output is partially correct
11 Partially correct 86 ms 26548 KB Output is partially correct
12 Partially correct 111 ms 28524 KB Output is partially correct
13 Partially correct 59 ms 24480 KB Output is partially correct
14 Partially correct 69 ms 23520 KB Output is partially correct
15 Partially correct 104 ms 28452 KB Output is partially correct
16 Runtime error 23 ms 30844 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -