Submission #960089

#	Time	Username	Problem	Language	Result	Execution time	Memory
960089		Pety	Logičari (COCI21_logicari)	C++14	110 / 110	97 ms	23108 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC target ("avx2")

using namespace std;

int viz[100002], dp[100002][2][2], n, nod1, nod2;
vector<int>G[100002];
int c1, c2;

void dfs (int x, int par) {
  viz[x] = 1;
  for (auto it : G[x]) {
    if (it != par) {
      if (viz[it]) {
        nod1 = x, nod2 = it;
      }
      else
        dfs(it, x);
    }
  }
}


void dfs (int x) {
  viz[x] = 1;
  vector<int>sons;
  for (auto it : G[x])
    if (!viz[it]){
      dfs(it);
      sons.push_back(it);
    }
  for (int par = 0; par < 2; par++)
    for (int c= 0; c < 2; c++) {
      if (x == nod1 && (c != c1 || par != 0))
        dp[x][c][par]= -1;
      else if (x == nod2 && (c != c2 || par + c1 == 2))
        dp[x][c][par] = -1;
      else {
        int sum = 0, prost = 0;
        for (auto it : sons) {
          if (dp[it][0][c] == -1) prost++;
          sum += dp[it][0][c];
        }
        if (par || (x == nod1 && c2) || (x == nod2 && c1)) 
          dp[x][c][par] = (!prost ? sum+c : -1);
        else {
          int mn  = 1e9;
          if (prost > 1) {
            dp[x][c][par] = -1;
            continue;
          }
          for (auto it : sons) {
            if (dp[it][0][c] == -1) {
              if (dp[it][1][c] != -1)
                mn = dp[it][1][c] - dp[it][0][c];
              else
                 mn = 1e9;
              break;
            }
            if (dp[it][1][c] != -1)
            mn = min(dp[it][1][c] - dp[it][0][c], mn);
          }
          if (mn != 1e9)
            dp[x][c][par] = mn+sum+c;
          else
            dp[x][c][par] = -1;
        }
      }
    }
    
}


int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 0);
//  cout << nod1 << " " << nod2 << "\n";

  int ans = 1e9;
  for (c1 = 0; c1 < 2; c1++)
    for (c2 = 0; c2 < 2; c2++) {
      memset(dp, 0, sizeof(dp));
      memset(viz, 0, sizeof(viz));
      dfs(nod1);
      if (dp[nod1][0][0] != -1) ans = min(ans, dp[nod1][0][0]);
      if (dp[nod1][1][0] != -1) ans = min(ans, dp[nod1][1][0]);
    }
  cout << ((ans == 1e9 || ans < 0) ? -1 : ans);
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50