216202026-01-13 17:21:47algoproEgyirányú egyensúlycpp17Wrong answer 2/5090ms9904 KiB
// UUID: f02c4040-4069-40da-b643-8c882506a80d
#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;
vector<int> ans;
void euler(int cs)
{
	while(tart[cs]<adj[cs].size())
	{
		int x=tart[cs];
		if(!volt[adj[cs][x][1]])
		{
			volt[adj[cs][x][1]]=1;
			euler(adj[cs][x][0]);
		}
		tart[cs]++;
	}
	ans.push_back(cs);
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m; cin>>n>>m;
	for(int i=0; i<m; i++)
	{
		int a,b; cin>>a>>b;
		if(a>b) swap(a,b),ford[i]=1;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
		elek.insert({a,b,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});
		adj[b].push_back({a,m});
	}
	for(int i=1; i<=n; i++)
		if(tart[i]<adj[i].size()) euler(i);
	vector<bool> bal(m);
	set<array<int, 2>> fuck;
	for(int i=1; i<ans.size(); i++)
	{
		int a=ans[i-1],b=ans[i];
		bool csere=0;
		if(a>b)
		{
			csere=1;
			swap(a,b);
		}
		array<int, 3> x{a,b,0};
		auto it=elek.lower_bound(x);
		if(it==elek.end() || (*it)[0]!=a || (*it)[1]!=b) continue;
		if(fuck.count({a,b})) continue;
		fuck.insert({a,b});
		int ind=(*it)[2];
		if(ford[ind]==csere) bal[ind]=1;
	}
	for(int i=0; i<m; i++)
		cout<<(bal[i]?"<-":"->")<<" ";
	cout<<"\n";
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Accepted0/02ms1588 KiB
2Wrong answer0/076ms8880 KiB
3Accepted2/22ms1588 KiB
4Wrong answer0/22ms1776 KiB
5Wrong answer0/22ms1588 KiB
6Wrong answer0/22ms1604 KiB
7Wrong answer0/22ms1588 KiB
8Wrong answer0/23ms1796 KiB
9Wrong answer0/22ms1588 KiB
10Wrong answer0/23ms1588 KiB
11Wrong answer0/24ms1604 KiB
12Wrong answer0/24ms1804 KiB
13Wrong answer0/317ms3124 KiB
14Wrong answer0/328ms4444 KiB
15Wrong answer0/332ms4452 KiB
16Wrong answer0/354ms7564 KiB
17Wrong answer0/317ms3152 KiB
18Wrong answer0/352ms6964 KiB
19Wrong answer0/352ms7000 KiB
20Wrong answer0/374ms8708 KiB
21Wrong answer0/390ms9680 KiB
22Wrong answer0/383ms9904 KiB