221582026-01-14 17:29:58algoproEgyirányú egyensúlycpp17Accepted 50/5050ms4804 KiB
// UUID: feab5091-2aa3-461a-b0d2-d78921344e98
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> szl;
vector<bool> vi;
vector<int> ans;
vector<array<int, 2>> el;

void euler(int v){
	while(szl[v].size()>0){
		auto[c, ind]=szl[v].back();
		szl[v].pop_back();
		if(!vi[ind]){
			vi[ind]=1;
			ans[ind]=v;
			euler(c);
		}
	}
}

int main() {
	int n, m; cin>>n>>m;
	szl.resize(n+1);
	el.resize(m+1);
	for(int i=1; i<=m; i++){
		int a, b; cin>>a>>b;
		szl[a].push_back({b, i});
		szl[b].push_back({a, i});
		el[i]={a, b};
	}
	int ti=m;
	for(int i=1; i<=n; i++){
		if(szl[i].size()%2){
			szl[0].push_back({i, ++ti});
			szl[i].push_back({0, ti});
			el.push_back({0, i});
		}
	}
	vi.resize(ti+1);
	ans.resize(ti+1);

	for(int i=1; i<=ti; i++){
		if(!vi[i]){
			euler(el[i][0]);
		}
	}

	cout<<ti-m<<endl;
	for(int i=1; i<=m; i++){
		if(ans[i]==el[i][0]){cout<<"-> ";}
		else{cout<<"<- ";}
	}

}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/037ms3576 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms500 KiB
6Accepted2/21ms352 KiB
7Accepted2/21ms316 KiB
8Accepted2/21ms316 KiB
9Accepted2/21ms316 KiB
10Accepted2/22ms316 KiB
11Accepted2/22ms564 KiB
12Accepted2/22ms316 KiB
13Accepted3/39ms1348 KiB
14Accepted3/320ms2976 KiB
15Accepted3/324ms3708 KiB
16Accepted3/326ms2640 KiB
17Accepted3/312ms2116 KiB
18Accepted3/326ms2276 KiB
19Accepted3/328ms2540 KiB
20Accepted3/337ms3972 KiB
21Accepted3/343ms3500 KiB
22Accepted3/350ms4804 KiB