216972026-01-13 18:11:02algoproEgyirányú egyensúlycpp17Elfogadva 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms2612 KiB
2Elfogadva0/024ms6104 KiB
3Elfogadva2/23ms2616 KiB
4Elfogadva2/23ms2640 KiB
5Elfogadva2/23ms2612 KiB
6Elfogadva2/23ms2612 KiB
7Elfogadva2/23ms2612 KiB
8Elfogadva2/24ms2648 KiB
9Elfogadva2/23ms2760 KiB
10Elfogadva2/24ms2668 KiB
11Elfogadva2/23ms2868 KiB
12Elfogadva2/24ms2684 KiB
13Elfogadva3/37ms3380 KiB
14Elfogadva3/313ms4272 KiB
15Elfogadva3/317ms5808 KiB
16Elfogadva3/316ms5688 KiB
17Elfogadva3/310ms4292 KiB
18Elfogadva3/316ms5020 KiB
19Elfogadva3/317ms4752 KiB
20Elfogadva3/324ms6060 KiB
21Elfogadva3/325ms5692 KiB
22Elfogadva3/328ms5980 KiB