#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