oj.uz

Submission #817019

# Submission time Handle Problem Language Result Execution time Memory
817019 2023-08-09T08:33:37 Z ono_de206 Parking (CEOI22_parking) C++14
20 / 100
 95 ms 16860 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10;
int v[mxn][2], done[mxn];
vector<pair<int, int>> g[mxn];

void go() {
	int n, m;
	cin >> n >> m;
	set<int> em;
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j < 2; j++) {
			cin >> v[i][j];
			if(v[i][j]) g[v[i][j]].eb(j, i);
		}
		if(v[i][0] == 0) em.in(i);
		else if(v[i][0] == v[i][1]) done[v[i][0]] = 1;
	}

	vector<pair<int, int>> ans;

	for(int i = 1; i <= n; i++) {
		if(done[i]) continue;
		sort(all(g[i]));
		if(g[i][0].ff == 1) {
			if(em.empty()) {
				cout << -1 << '\n';
				return;
			}
			int x = *em.begin();
			ans.eb(g[i][0].ss, x);
			ans.eb(g[i][1].ss, x);
			v[g[i][0].ss][1] = v[g[i][1].ss][1] = 0;
			em.erase(x);
			v[x][0] = v[x][1] = i;
			done[i] = 1;
		}
	}

	function<void(int)> dfs = [&](int x) -> void {
		if(done[x]) return;
		if(g[x][1].ff == 0 && v[g[x][0].ss][1] == 0 && v[g[x][1].ss][1] == 0) {
			em.in(g[x][0].ss);
			ans.eb(g[x][0].ss, g[x][1].ss);
			v[g[x][0].ss][0] = 0;
			done[x] = 1;
		} else if(g[x][1].ff == 1 && v[g[x][0].ss][1] == 0) {
			ans.eb(g[x][1].ss, g[x][0].ss);
			v[g[x][1].ss][1] = 0;
			done[x] = 1;
			dfs(v[g[x][1].ss][0]);
		}
	};

	for(int i = 1; i <= n; i++) {
		if(done[i]) continue;
		dfs(i);
	}
	for(int i = 1; i <= n; i++) {
		if(done[i]) continue;
		assert(g[i][1].ff == 1);
		int x = g[i][0].ss, y = g[i][1].ss;
		if(em.empty()) {
			cout << -1 << '\n';
			return;
		}
		int p = *em.begin();
		ans.eb(y, p);
		v[y][1] = 0;
		v[p][0] = i;
		g[i][1] = {0, p};
		dfs(v[y][0]);
	}
	for(int i = 1; i <= n; i++) {
		if(!done[i]) {
			cout << -1 << '\n';
			return;
		}
	}
	cout << ans.size() << '\n';
	for(auto it : ans) {
		cout << it << '\n';
	}
}
 
signed main() {
	// #ifndef ONO
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Compilation message

Main.cpp: In function 'void go()':
Main.cpp:108:7: warning: unused variable 'x' [-Wunused-variable]
  108 |   int x = g[i][0].ss, y = g[i][1].ss;
      |       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16476 KB Output is correct
2 Correct 92 ms 16624 KB Output is correct
3 Correct 95 ms 16192 KB Output is correct
4 Correct 69 ms 16184 KB Output is correct
5 Correct 79 ms 16860 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 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 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 83 ms 16476 KB Output is correct
12 Correct 92 ms 16624 KB Output is correct
13 Correct 95 ms 16192 KB Output is correct
14 Correct 69 ms 16184 KB Output is correct
15 Correct 79 ms 16860 KB Output is correct
16 Incorrect 3 ms 4948 KB Output isn't correct
17 Halted 0 ms 0 KB -