This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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