216032026-01-13 17:06:35algoproEgyirányú egyensúlycpp17Elfogadva 50/5026ms3636 KiB
// UUID: 59da57c5-7e13-4102-9bbf-f47eaa703a79

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG
namespace debug {
int dbg_rec = 0;
 
template <typename T, typename... U>
concept IsAnyOf = (std::same_as<T, U> || ...);
 
template<typename T>
concept IsCont = IsAnyOf<T, std::vector<typename T::value_type>, 
std::set<typename T::value_type>,
std::multiset<typename T::value_type>>;
 
template<typename Ostream, IsCont Cont> 
Ostream& operator<<(Ostream& os,  const Cont v){ os<<"["; for(auto& x : v){os<<x<<", ";} os<<"]"; return os; }
 
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    os<<"{"<<p.first<<", "<<p.second<<"}"; return os;
}
 
template<typename T>
void print_dbg(stringstream& ss, T x) { ss << x; }
template<typename T, typename... Args>
void print_dbg(stringstream& ss, T x, Args... args) { ss << x << ", "; print_dbg(ss, args...); }
}
#define dbg(...) {stringstream ss; ++debug::dbg_rec; debug::print_dbg(ss, __VA_ARGS__); --debug::dbg_rec; cerr << string(debug::dbg_rec, '\t') << "\e[91m" << __func__ << ":" << __LINE__ << '\t' << #__VA_ARGS__ << " = " << ss.str() << "\e[39m" << endl; }
#define ASSERT(x) assert((x))
#else
#define dbg(...)
#define ASSERT(x)
#endif
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct edge {
    int u, idx, id;
};

vector<vector<edge>> g;
vector<int> pos;
vector<bool> dir;
int n, m;

void add_edge(int x, int y, int id) {
    g[x].push_back(edge{y, (int)g[y].size(), id});
    g[y].push_back(edge{x, (int)g[x].size() - 1, ~id});
}

void euler(int x) {
    while(pos[x] < g[x].size()) {
        edge e = g[x][pos[x]];
        ++pos[x];
        if(e.u == -1) continue;
        g[e.u][e.idx].u = -1;
        int i = e.id >= 0 ? e.id : ~e.id;
        if(i < m) dir[i] = e.id >= 0;
        //cout << x << " -> " << e.u << '\n';
        euler(e.u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    g.assign(n, vector<edge>());
    dir.assign(m, false);
    pos.assign(n, 0);
    vector<int> d(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin>>a>>b;
        --a, --b;
        add_edge(a, b, i);
        d[a]++;
        d[b]++;
    }
    
    vector<int> q;
    for(int i = 0; i < n; i++) if(d[i] % 2 == 1) q.push_back(i);

    for(int i = 0; i < (int)q.size(); i += 2) {
        add_edge(q[i], q[i+1], m);
    }

    for(int i = 0; i < n; i++) euler(i);

    cout << q.size() << '\n';

    for(int i = 0; i < m; i++) {
        if(dir[i]) {
            cout << "->";
        } else {
            cout << "<-";
        }
        cout << " ";
    }
    cout << '\n';

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/020ms3380 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms560 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/21ms316 KiB
9Elfogadva2/21ms316 KiB
10Elfogadva2/21ms316 KiB
11Elfogadva2/22ms316 KiB
12Elfogadva2/22ms512 KiB
13Elfogadva3/36ms1076 KiB
14Elfogadva3/310ms2100 KiB
15Elfogadva3/314ms3124 KiB
16Elfogadva3/314ms2840 KiB
17Elfogadva3/38ms2036 KiB
18Elfogadva3/314ms2492 KiB
19Elfogadva3/314ms2396 KiB
20Elfogadva3/320ms3380 KiB
21Elfogadva3/323ms3124 KiB
22Elfogadva3/326ms3636 KiB