216202026-01-13 17:21:47algoproEgyirányú egyensúlycpp17Hibás válasz 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/50
1Elfogadva0/02ms1588 KiB
2Hibás válasz0/076ms8880 KiB
3Elfogadva2/22ms1588 KiB
4Hibás válasz0/22ms1776 KiB
5Hibás válasz0/22ms1588 KiB
6Hibás válasz0/22ms1604 KiB
7Hibás válasz0/22ms1588 KiB
8Hibás válasz0/23ms1796 KiB
9Hibás válasz0/22ms1588 KiB
10Hibás válasz0/23ms1588 KiB
11Hibás válasz0/24ms1604 KiB
12Hibás válasz0/24ms1804 KiB
13Hibás válasz0/317ms3124 KiB
14Hibás válasz0/328ms4444 KiB
15Hibás válasz0/332ms4452 KiB
16Hibás válasz0/354ms7564 KiB
17Hibás válasz0/317ms3152 KiB
18Hibás válasz0/352ms6964 KiB
19Hibás válasz0/352ms7000 KiB
20Hibás válasz0/374ms8708 KiB
21Hibás válasz0/390ms9680 KiB
22Hibás válasz0/383ms9904 KiB