Cod sursa(job #3213217)

Utilizator sandry24Grosu Alexandru sandry24 Data 12 martie 2024 18:42:07
Problema Algoritmul lui Gauss Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
 
int n, m;
vector<vi> adj(200005), adj_inv(200005);
vector<bool> visited(200005), assign(100005);
vi order, comp(200005);
 
void dfs(int x){
    visited[x] = 1;
    for(auto i : adj[x]){
        if(!visited[i])
            dfs(i);
    }
    order.pb(x);
}
 
void dfs2(int x, int cnt){
    visited[x] = 1;
    comp[x] = cnt;
    for(auto i : adj_inv[x]){
        if(!visited[i])
            dfs2(i, cnt);
    }
}
 
void solve(){
    cin >> n >> m;
    int maxm = 2*m;
    for(int i = 0; i < n; i++){
        int a, b;
        char c1, c2;
        cin >> c1 >> a >> c2 >> b;
        a--; b--;
        a = 2*a ^ (c1 == '-');
        b = 2*b ^ (c2 == '-');
        int neg_a = a ^ 1;
        int neg_b = b ^ 1;
        adj[neg_a].pb(b); adj[neg_b].pb(a);
        adj_inv[b].pb(neg_a); adj_inv[a].pb(neg_b);
    }
    for(int i = 0; i < maxm; i++){
        if(!visited[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    int cnt = 0;
    visited = vector<bool>(200005);
    for(int i = 0; i < maxm; i++){
        int x = order[i];
        if(!visited[x]){
            dfs2(x, cnt);
            cnt++;
        }
    }
    for(int i = 0; i < maxm; i += 2){
        if(comp[i] == comp[i+1]){
            cout << "IMPOSSIBLE\n";
            return;
        }
        assign[i / 2] = (comp[i] > comp[i+1]);
    }
    for(int i = 0; i < m; i++)
        cout << (assign[i] ? '+' : '-') << ' ';
}
 
int main(){
    //freopen("problema3.in", "r", stdin);
    //freopen("magazin.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}