216972026-01-13 18:11:02algoproEgyirányú egyensúlycpp17Accepted 50/5028ms6104 KiB
// UUID: 39a7ce70-e419-4c82-b57a-c232a61e1a84
#include <bits/stdc++.h>
using namespace std;
const int c=1e5+321;
bool volt[c],ford[c];
vector<array<int, 2>> adj[c];
int tart[c];
set<array<int, 3>> elek;
bool jobb[c];
int m;
vector<int> ans;
void euler(int cs)
{
	while(tart[cs]<adj[cs].size())
	{
		int x=tart[cs];
		tart[cs]++;
		if(!volt[adj[cs][x][1]])
		{
			int a=cs,b=adj[cs][x][0];
			if(adj[cs][x][1]<m)
			{
				bool csere=0;
				if(a>b) csere=1;
				if(csere==ford[adj[cs][x][1]]) jobb[adj[cs][x][1]]=1;
			}
			volt[adj[cs][x][1]]=1;
			euler(adj[cs][x][0]);
		}
	}
	ans.push_back(cs);
}
vector<array<int, 2>> geci;
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n>>m;
	for(int i=0; i<m; i++)
	{
		int a,b; cin>>a>>b;
		geci.push_back({a,b});
		if(a>b) swap(a,b),ford[i]=1;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
	}
	vector<int> pt;
	for(int i=1; i<=n; i++)
		if((adj[i].size())%2) pt.push_back(i);
	cout<<pt.size()<<"\n";
	for(int i=0; i<pt.size(); i+=2)
	{
		int a=pt[i],b=pt[i+1];
		adj[a].push_back({b,m+i});
		adj[b].push_back({a,m+i});
	}
	for(int j=1; j<=n; j++)
	{
		ans.clear();
		euler(j);
	}
	vector<int> fox(n+1);
	for(int i=0; i<m; i++)
	{
		if(jobb[i]) fox[geci[i][0]]--,fox[geci[i][1]]++;
		else fox[geci[i][1]]--,fox[geci[i][0]]++;
	}
	int mx=0;
	for(int i=1; i<=n; i++)
		mx=max(mx,abs(fox[i]));
	for(int i=0; i<m; i++)
	{
		cout<<(jobb[i]?"<-":"->")<<" ";
	}
	cout<<"\n";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms2612 KiB
2Accepted0/024ms6104 KiB
3Accepted2/23ms2616 KiB
4Accepted2/23ms2640 KiB
5Accepted2/23ms2612 KiB
6Accepted2/23ms2612 KiB
7Accepted2/23ms2612 KiB
8Accepted2/24ms2648 KiB
9Accepted2/23ms2760 KiB
10Accepted2/24ms2668 KiB
11Accepted2/23ms2868 KiB
12Accepted2/24ms2684 KiB
13Accepted3/37ms3380 KiB
14Accepted3/313ms4272 KiB
15Accepted3/317ms5808 KiB
16Accepted3/316ms5688 KiB
17Accepted3/310ms4292 KiB
18Accepted3/316ms5020 KiB
19Accepted3/317ms4752 KiB
20Accepted3/324ms6060 KiB
21Accepted3/325ms5692 KiB
22Accepted3/328ms5980 KiB