Submission #635469

#	Time	Username	Problem	Language	Result	Execution time	Memory
635469		Markomafko972	Parking (CEOI22_parking)	C++14	100 / 100	554 ms	47500 KiB

Main

#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];
int dist[200005];
queue<int> q;

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

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

void bfs() {
	
	while (!q.empty()) {
		int cvor = q.front();
		q.pop();
		
		for (int i = 0; i < v[cvor].size(); i++) {
			if (dist[v[cvor][i]] == -1) {
				dist[v[cvor][i]] = dist[cvor]+1;
				q.push(v[cvor][i]);
			}
		}
	}
	
}

int main() {

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

	memset(dist, -1, sizeof dist);
    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();
        }
        
        for (int j = 0; j < tren.size(); j++) {
        	if ((int)smj[tren[j].X].size() == 0 && tren[j].Y == 0) {
        		q.push(tren[j].X);
        		dist[tren[j].X] = 0;
        		break;
			}
		}
		
		if (q.size() == 0) {
			for (int j = 0; j < tren.size(); j++) {
				if ((int)smj[tren[j].X].size() == 1 && tren[j].Y == 1) {
					q.push(tren[j].X);
					dist[tren[j].X] = 0;
					break;
				}
			}
		}
		
		if (q.size() == 0) {
			q.push(tren[0].X);
			dist[tren[0].X] = 0;
		}
		
		bfs();
        
        tocke.clear();
        for (int j = 0; j < tren.size(); j++) {
        	//cout << tren[j].X << " " << (int)smj[tren[j].X].size() << " " << 1-tren[j].Y << endl;
        	znak[tren[j].X] = 1-tren[j].Y;
        	dalje[tren[j].X] = (int)smj[tren[j].X].size();
        	tocke.insert({{(int)smj[tren[j].X].size(), 1-tren[j].Y}, {dist[tren[j].X], tren[j].X}});
		}

        for (int abc = 0; abc < tren.size(); abc++) {
            int novi = -1, w = 0;
			
			pair< pair<int, int>, pair<int, int> > broj = *tocke.begin();
            tocke.erase(tocke.begin());
        	novi = broj.Y.Y;
            w = 1 - broj.X.Y;
            
            //cout << "reshi " << novi << " " << w << " " << pr.size() << endl;
            	
            for (int j = 0; j < pravi[novi].size(); j++) {
            	int susjed = pravi[novi][j];
            	if (tocke.find({{dalje[susjed], znak[susjed]}, {dist[susjed], susjed}}) != tocke.end()) {
					tocke.erase({{dalje[susjed], znak[susjed]}, {dist[susjed], susjed}});
            		dalje[susjed]--;
            		tocke.insert({{dalje[susjed], znak[susjed]}, {dist[susjed], susjed}});
            	}
			}

            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 (stderr)

Main.cpp: In function 'void dfs(int)':
Main.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < v[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void rek(int)':
Main.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < v[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void bfs()':
Main.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int i = 0; i < v[cvor].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:130: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]
  130 |     for (int i = 0; i < svi.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:150: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]
  150 |         for (int j = 0; j < tren.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:165: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]
  165 |         for (int j = 0; j < tren.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |    for (int j = 0; j < tren.size(); j++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp:191: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]
  191 |         for (int j = 0; j < tren.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:198: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]
  198 |         for (int abc = 0; abc < tren.size(); abc++) {
      |                           ~~~~^~~~~~~~~~~~~
Main.cpp:208:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |             for (int j = 0; j < pravi[novi].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:234:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |     for (int i = 0; i < out.size(); i++) cout << out[i].X+1 << " " << out[i].Y+1 << "\n";
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15