oj.uz

Submission #369894

# Submission time Handle Problem Language Result Execution time Memory
369894 2021-02-22T17:29:18 Z ivan_tudor Love Polygon (BOI18_polygon) C++14
54 / 100
 479 ms 28900 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
map<string, int> id;
map<pair<int, int>, int> edges;
vector<int> gr[N];
int mchtree[N][2];
bool viz[N];
void dfsdown(int nod,int dad1,int dad2){
  viz[nod] = true;
  int maxdif = INT_MIN;
  for(int x:gr[nod]){
    if(x!=dad1 && x!=dad2 && x!= nod){
      dfsdown(x, nod, 0);
      mchtree[nod][0] += max(mchtree[x][0], mchtree[x][1]);
      maxdif = max(maxdif, mchtree[x][0] + 1 - max(mchtree[x][0], mchtree[x][1]));
    }
  }
  if(maxdif != INT_MIN)
    mchtree[nod][1] = mchtree[nod][0] + maxdif;
}

stack<int> activ;
int dfs_cycle(int nod, int prev){
  activ.push(nod);
  viz[nod] = true;
  for(auto x:gr[nod]){
    if(viz[x] == false){
      int val = dfs_cycle(x, nod);
      if(val != -1)
        return val;
    }
    else if(x!= prev && viz[x] == true){
      return x;
    }
  }
  activ.pop();
  return -1;
}
int mch[N][2];
int makedp(vector<int> &cycle, int l,int r){
  if(l > r)
    return 0;
  mch[l][0] = mchtree[cycle[l]][0], mch[l][1] = mchtree[cycle[l]][1];
  for(int i=l + 1; i<=r;i++){
    int nod = cycle[i];
    mch[i][1] = max(mchtree[nod][1] + max(mch[i-1][0], mch[i-1][1]), mchtree[nod][0] + 1 + mch[i-1][0]);
    mch[i][0] = max(mch[i-1][0], mch[i-1][1]) + mchtree[nod][0];
  }
  return max(mch[r][0], mch[r][1]);
}
int solve_cycle(vector<int> &cycle){
  int csize = cycle.size();
  for(int i=0;i<cycle.size();i++){
    int next = cycle[(i + 1)%csize], prev = cycle[(i - 1 + csize)%csize];
    dfsdown(cycle[i], next, prev);
  }
  int answer = 0;
  // pot lua 0 - csize -1; 0 -1; 0 blocat din copac sau gol
  int ansc = 1 + mchtree[cycle[0]][0] + mchtree[cycle[csize - 1]][0] + makedp(cycle, 1, csize - 2);
  answer = max(answer, ansc);

  ansc = 1 + mchtree[cycle[0]][0] + mchtree[cycle[1]][0] + makedp(cycle, 2, csize - 1);
  answer = max(answer, ansc);

  ansc = max(mchtree[cycle[0]][0], mchtree[cycle[0]][1]) + makedp(cycle, 1, csize - 1);
  answer = max(answer, ansc);
  return answer;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n = 0;
  int m;
  cin>>m;
  for(int i=1;i<=m;i++){
    string s;
    int x, y;
    cin>>s;
    if(!id.count(s))
      id[s] = ++n;
    x = id[s];
    cin>>s;
    if(!id.count(s))
      id[s] = ++n;
    y = id[s];
    if(x > y)
      swap(x, y);
    if(edges.count({x, y})){
      edges[{x, y}]++;
      continue;
    }
    if(x != y){
      gr[x].push_back(y);
      gr[y].push_back(x);
    }
    edges[{x,y}] = 1;
  }
  if(n%2 == 1){
    cout<<"-1";
    return 0;
  }
  int answer = 0;
  for(int i=1;i<=n;i++){
    if(viz[i] == false){
      if(gr[i].size() == 1){
        int other = gr[i][0];
        if(gr[other].size() ==1){
          viz[i] = viz[other] = 1;
          answer++;
          if(edges[{min(i, other), max(i, other)}] == 2)
            answer++;
          continue;
        }

      }
      activ = stack<int>();
      int valcyc = dfs_cycle(i, 0);
      if(valcyc == -1){
        dfsdown(i, 0, 0);
        answer+= max(mchtree[i][0], mchtree[i][1]);
      }
      else{
        vector<int> cycle;
        do{
          cycle.push_back(activ.top());
          activ.pop();
        }while(cycle.end()[-1] != valcyc);
        answer+= solve_cycle(cycle);
      }
    }
  }
  cout<< n - answer;
  return 0;
}

Compilation message

polygon.cpp: In function 'int solve_cycle(std::vector<int>&)':
polygon.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0;i<cycle.size();i++){
      |               ~^~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Incorrect 2 ms 2668 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 479 ms 27928 KB Output is correct
5 Correct 407 ms 20736 KB Output is correct
6 Correct 474 ms 28900 KB Output is correct
7 Correct 383 ms 20844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 20844 KB Output is correct
2 Correct 432 ms 22252 KB Output is correct
3 Correct 274 ms 16876 KB Output is correct
4 Correct 387 ms 20076 KB Output is correct
5 Correct 435 ms 25648 KB Output is correct
6 Correct 458 ms 20928 KB Output is correct
7 Correct 418 ms 20972 KB Output is correct
8 Correct 347 ms 19948 KB Output is correct
9 Correct 424 ms 21100 KB Output is correct
10 Correct 256 ms 20452 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2796 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Incorrect 2 ms 2668 KB Output isn't correct
9 Halted 0 ms 0 KB -