216952026-01-13 18:10:37algoproEgyirányú egyensúlycpp17Runtime error 44/5025ms5020 KiB
// UUID: 6c7ab774-d15f-4ebf-a991-d318263b866b
#include <bits/stdc++.h>
using namespace std;
const int c=5e4+20;
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
base44/50
1Accepted0/02ms1588 KiB
2Accepted0/023ms5020 KiB
3Accepted2/22ms1588 KiB
4Accepted2/22ms1588 KiB
5Accepted2/22ms1464 KiB
6Accepted2/22ms1588 KiB
7Accepted2/22ms1384 KiB
8Accepted2/22ms1588 KiB
9Accepted2/23ms1588 KiB
10Accepted2/23ms1592 KiB
11Accepted2/23ms1588 KiB
12Accepted2/23ms1588 KiB
13Accepted3/37ms2100 KiB
14Accepted3/313ms2992 KiB
15Accepted3/314ms4528 KiB
16Accepted3/314ms4324 KiB
17Accepted3/38ms3216 KiB
18Accepted3/314ms3828 KiB
19Accepted3/317ms3760 KiB
20Accepted3/321ms4844 KiB
21Runtime error0/325ms4440 KiB
22Runtime error0/324ms4820 KiB