oj.uz

Submission #960082

# Submission time Handle Problem Language Result Execution time Memory
960082 2024-04-09T15:46:41 Z Pety Logičari (COCI21_logicari) C++14
10 / 110
 112 ms 23112 KB 
#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 && dp[it][1][c] != -1) {
              mn = dp[it][1][c] - dp[it][0][c];
              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);
  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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 98 ms 23112 KB Output is correct
6 Correct 112 ms 22868 KB Output is correct
7 Correct 95 ms 23064 KB Output is correct
8 Correct 90 ms 22864 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4744 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4744 KB Output is correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 98 ms 23112 KB Output is correct
6 Correct 112 ms 22868 KB Output is correct
7 Correct 95 ms 23064 KB Output is correct
8 Correct 90 ms 22864 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4744 KB Output is correct
11 Incorrect 1 ms 4700 KB Output isn't correct
12 Halted 0 ms 0 KB -