oj.uz

Submission #293894

# Submission time Handle Problem Language Result Execution time Memory
293894 2020-09-08T13:35:07 Z 임성재(#5816) None (balkan16_acrobat) C++17
0 / 100
 22 ms 28576 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace 
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
set<int> A[300010];
set<int> B[300010];
int cnt[300010];
vector<pair<int, pii>> ans;

int main() {
	fast;

	cin >> n >> m;

	for(int i=1; i<=m; i++) {
		int a, b;
		cin >> a >> b;

		if(a == b) {
			cnt[a]++;
		}
		else {
			A[a].insert(b);
			B[b].insert(a);
		}
	}

	for(int i=1; i<=n; i++) {
		if((A[i].size() + cnt[i]) % 2 == 1) {
			if(A[i].size()) {
				int x = *A[i].begin();
				A[i].erase(x);
				B[x].erase(i);

				ans.eb(1, mp(i, x));

				if(A[x].find(i) == A[x].end()) {
					A[x].insert(i);
					B[i].insert(x);
				}			
				else {
					A[x].erase(i);
					B[i].erase(x);
				}
			}
			else if(B[i].size()) {
				int x = *B[i].begin();
				B[i].erase(x);
				A[x].erase(i);

				ans.eb(1, mp(x, i));

				if(B[x].find(i) == B[x].end()) {
					B[x].insert(i);
					A[i].insert(x);
				}			
				else {
					B[x].erase(i);
					A[i].erase(x);
				}
			}
			else {
				cout << -1;
				return 0;
			}
		}

		for(auto j : A[i]) {
			B[j].erase(i);
		}

		A[i].clear();

		for(auto j : B[i]) {
			A[j].erase(i);
			cnt[j]++;
		}

		B[i].clear();
	}

	cout << ans.size() + n << "\n";
	for(auto i : ans) {
		cout << i.fi << " " << i.se.fi << " " << i.se.se << "\n";
	}

	for(int i=1; i<n; i++) {
		cout << 2 << " " << i << " " << i+1 << "\n";
	}
	cout << 2 << " " << n << " " << 1 << endl;
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Incorrect 20 ms 28544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Incorrect 22 ms 28576 KB Output isn't correct
3 Halted 0 ms 0 KB -