Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.