fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4. int n, root, src;
  5. int par[100005], dp[100005][4];
  6. int sforcecolor = -1;
  7. int rblue = -1;
  8. bool visited[100005];
  9. vector<int> adj[100005];
  10. int add(int a, int b)
  11. {
  12.     if (a >= INF || b >= INF) return INF;
  13.     return a + b;
  14. }
  15. void cc(int u, int p)
  16. {
  17.     if (root) return;
  18.     visited[u] = true;
  19.     par[u] = p;
  20.     for (int v : adj[u])
  21.     {
  22.         if (v == p) continue;
  23.         if (visited[v])
  24.         {
  25.             if (root == 0)
  26.             {
  27.                 root = v;
  28.                 src = u;
  29.                 return;
  30.             }
  31.         }
  32.         else
  33.         {
  34.             cc(v, u);
  35.             if (root) return;
  36.         }
  37.     }
  38. }
  39. void dfsdp(int u, int p)
  40. {
  41.     int sum0 = 0, cntw0 = 0;
  42.     int sum1 = 0, cntw1 = 0;
  43.     vector<int> child;
  44.     for (int v : adj[u])
  45.         if (v != p)
  46.         {
  47.             child.push_back(v);
  48.             dfsdp(v, u);
  49.         }
  50.     for (int v : child)
  51.     {
  52.         if (dp[v][0] >= INF) cntw0++;
  53.         else sum0 += dp[v][0];
  54.         if (dp[v][1] >= INF) cntw1++;
  55.         else sum1 += dp[v][1];
  56.     }
  57.     int res0 = INF;
  58.     for (int v : child)
  59.     {
  60.         int val = dp[v][2];
  61.         int remain = (dp[v][0] >= INF) ? (cntw0 == 1 ? sum0 : INF) : (cntw0 == 0 ? sum0 - dp[v][0] : INF);
  62.         res0 = min(res0, add(val, remain));
  63.     }
  64.     dp[u][0] = res0;
  65.     dp[u][1] = (cntw0 == 0) ? sum0 : INF;
  66.     int res2 = INF;
  67.     for (int v : child)
  68.     {
  69.         int val = dp[v][3];
  70.         int remain = (dp[v][1] >= INF) ? (cntw1 == 1 ? sum1 : INF) : (cntw1 == 0 ? sum1 - dp[v][1] : INF);
  71.         res2 = min(res2, add(1, add(val, remain)));
  72.     }
  73.     dp[u][2] = res2;
  74.     dp[u][3] = (cntw1 == 0) ? add(1, sum1) : INF;
  75.     if (u == src)
  76.     {
  77.         int childwhite = dp[u][0];
  78.         int nowhite    = dp[u][1];
  79.         int childblue  = dp[u][2];
  80.         int noblue     = dp[u][3];
  81.         dp[u][0] = dp[u][1] = dp[u][2] = dp[u][3] = INF;
  82.         if (rblue)
  83.         {
  84.             dp[u][0] = nowhite;
  85.             dp[u][1] = INF;
  86.             dp[u][2] = noblue;
  87.             dp[u][3] = INF;
  88.         }
  89.         else
  90.         {
  91.             dp[u][0] = childwhite;
  92.             dp[u][1] = nowhite;
  93.             dp[u][2] = childblue;
  94.             dp[u][3] = noblue;
  95.         }
  96.         if (sforcecolor == 0)
  97.             dp[u][2] = dp[u][3] = INF;
  98.         else
  99.             dp[u][0] = dp[u][1] = INF;
  100.     }
  101. }
  102. int caseoh(int rcolor, int scolor)
  103. {
  104.     sforcecolor = scolor;
  105.     rblue = rcolor;
  106.     int dpstate = -1;
  107.     if (rcolor == 0 && scolor == 0) dpstate = 0;
  108.     else if (rcolor == 0 && scolor == 1) dpstate = 1;
  109.     else if (rcolor == 1 && scolor == 0) dpstate = 2;
  110.     else dpstate = 3;
  111.     dfsdp(root, 0);
  112.     return dp[root][dpstate];
  113. }
  114. int main()
  115. {
  116.     ios_base::sync_with_stdio(0);
  117.     cin.tie(0);
  118.     cout.tie(0);
  119.     if (fopen("PAINT.inp", "r"))
  120.     {
  121.         freopen("PAINT.inp", "r", stdin);
  122.         freopen("PAINT.out", "w", stdout);
  123.     }
  124.     cin >> n;
  125.     for (int i = 1, u, v; i <= n; i++)
  126.     {
  127.         cin >> u >> v;
  128.         adj[u].push_back(v);
  129.         adj[v].push_back(u);
  130.     }
  131.     cc(1, 0);
  132.     for (int &v : adj[root])
  133.         if (v == src)
  134.         {
  135.             v = adj[root].back();
  136.             adj[root].pop_back();
  137.             break;
  138.         }
  139.     for (int &v : adj[src])
  140.         if (v == root)
  141.         {
  142.             v = adj[src].back();
  143.             adj[src].pop_back();
  144.             break;
  145.         }
  146.     int ans = INF;
  147.     ans = min(ans, caseoh(0, 0));
  148.     ans = min(ans, caseoh(0, 1));
  149.     ans = min(ans, caseoh(1, 0));
  150.     ans = min(ans, caseoh(1, 1));
  151.     if (ans >= INF) cout << -1;
  152.     else cout << ans;
  153.     return 0;
  154. }
  155.  
Success #stdin #stdout 0.01s 6152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/EWYlMD
language:
C++14 (gcc 8.3)
created:
3 days 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!