acm-lounges.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <bitset>
using namespace std;

typedef set<pair<int, int> > spi;
const int MAX_N = 200000;

bitset<MAX_N> lounge;
bitset<MAX_N> color;

struct edge {
    int w;
    int n[2];

    edge(){}
    edge(int a, int b, int weight) {
        n[0] = a;
        n[1] = b;
        w = weight;
    }
};

bool fillAndCheck (int start, vector<spi> &graph, bitset<MAX_N> &visited) {
    visited[start] = true;
    bool good = true;

    for (spi::iterator it = graph[start].begin(); it != graph[start].end(); it++) {
        int idx = (*it).first;
        int val = (*it).second;

        if (visited[idx]) {
            // check
            if (val == 0 || val == 2) {
                good = (lounge[idx] == lounge[start]);
            } else {
                good = (lounge[idx] != lounge[start]);
            }

            if (! good)
                return false;
        } else {
            // fill
            if (val == 0 || val == 2) {
                lounge[idx] = lounge[start];
            } else {
                lounge[idx] = !lounge[start];
            }

            good = fillAndCheck(idx, graph, visited);
            if (! good) return false;
        }
    }

    return true;
}

bool colorAndCount(int start, vector<spi> &graph, bitset<MAX_N> &visited, int* red, int* black) {
    visited[start] = true;
    bool good;

    for (spi::iterator it = graph[start].begin(); it != graph[start].end(); it++) {
        int idx = (*it).first;
        int val = (*it).second;

        if (visited[idx]) {
            // check
            good = (color[idx] != color[start]);
            if (! good) return false;
        } else {
            // note that there should be no 2s or 0s here
            color[idx] = !color[start];
            if (color[idx]) {
                *red = *red + 1;
                //cerr << "coloring " << idx << " red" << endl;
            } else {
                *black = *black + 1;
                //cerr << "coloring " << idx << " black" << endl;
            }

            good = colorAndCount(idx, graph, visited, red, black);
            if (!good) return false;
        }
    }

    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<spi> graph (n);
    vector<edge> edges (m);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--;
        b--;

        graph[a].insert(make_pair(b, w));
        graph[b].insert(make_pair(a, w));
        edges[i] = edge(a, b, w);
    }

    // floodfill
    bitset<MAX_N> visited;
    bool good = true;

    // first fill in known values
    // works on basis of connected components
    for (int i = 0; i < m; i++) {
        if (edges[i].w == 1) continue;

        int val = edges[i].w;

        for (int j = 0; j < 2; j++) {
            int start = edges[i].n[j];

            lounge[start] = (val == 2);
            good = fillAndCheck(start, graph, visited);

            if (! good) break;
        }

        if (! good) break;
    }

    int numLounges = lounge.count();

    if (good) {
        // then fill in UNKNOWN -> connected components made up of 1s
        for (int i = 0; i < m; i++) {
            int val = edges[i].w;
            for (int j = 0; j < 2; j++) {
                int start = edges[i].n[j];

                // have already looked at this connected component
                if (visited[start]) continue;

                int red = 0;
                int black = 0;

                // color myself red
                color[start] = true;
                red++;

                good = colorAndCount(start, graph, visited, &red, &black);
                if (! good) break;

                numLounges += min(red, black);

            }

            if (! good) break;
        }
    }


    if (good)
        cout << numLounges << endl;
    else
        cout << "impossible" << endl;
}