fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define maxn 200005
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. int n, m;
  12. int c[maxn], d[maxn];
  13. vector<int> adj[maxn];
  14.  
  15. int col[maxn]; // -1: chưa thăm, 0/1: hai phía
  16. vector<int> comp;
  17.  
  18. bool ok;
  19.  
  20. void dfs(int u) {
  21.     comp.push_back(u);
  22.  
  23.     for (int v : adj[u]) {
  24.         if (col[v] == -1) {
  25.             col[v] = col[u] ^ 1;
  26.             dfs(v);
  27.         } else if (col[v] == col[u]) {
  28.             ok = false;
  29.         }
  30.     }
  31. }
  32.  
  33. signed main() {
  34.     itachi;
  35.  
  36.     cin >> n >> m;
  37.     for (int i = 1; i <= n; i++) cin >> c[i];
  38.     for (int i = 1; i <= n; i++) cin >> d[i];
  39.  
  40.     for (int i = 1; i <= m; i++) {
  41.         int u, v;
  42.         cin >> u >> v;
  43.         adj[u].push_back(v);
  44.         adj[v].push_back(u);
  45.     }
  46.  
  47.     memset(col, -1, sizeof(col));
  48.  
  49.     int ans = 0;
  50.  
  51.     for (int i = 1; i <= n; i++) {
  52.         if (col[i] != -1) continue;
  53.  
  54.         comp.clear();
  55.         ok = true;
  56.  
  57.         col[i] = 0;
  58.         dfs(i);
  59.  
  60.         if (!ok) {
  61.             cout << -1;
  62.             return 0;
  63.         }
  64.  
  65.         int cost0 = 0, cost1 = 0;
  66.         bool bad0 = false, bad1 = false;
  67.  
  68.         for (int u : comp) {
  69.             int orig = c[u] - 1;
  70.  
  71.             int need0 = col[u];
  72.             int need1 = col[u] ^ 1;
  73.  
  74.             if (orig != need0) {
  75.                 if (!d[u]) bad0 = true;
  76.                 else cost0++;
  77.             }
  78.             if (orig != need1) {
  79.                 if (!d[u]) bad1 = true;
  80.                 else cost1++;
  81.             }
  82.         }
  83.  
  84.         if (bad0 && bad1) {
  85.             cout << -1;
  86.             return 0;
  87.         } else if (bad0) {
  88.             ans += cost1;
  89.         } else if (bad1) {
  90.             ans += cost0;
  91.         } else {
  92.             ans += min(cost0, cost1);
  93.         }
  94.     }
  95.  
  96.     cout << ans;
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 11036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h09eMr
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!