Submission #369910

#	Time	Username	Problem	Language	Result	Execution time	Memory
369910		ivan_tudor	Love Polygon (BOI18_polygon)	C++14	100 / 100	511 ms	35044 KiB

polygon

#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) || (x == prev && edges[{min(x, nod), max(x, nod)}] == 2)){
      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);
  if(csize == 2)
    ansc++; // caz part
  answer = max(answer, ansc);

  ansc = 1 + mchtree[cycle[0]][0] + mchtree[cycle[1]][0] + makedp(cycle, 2, csize - 1);
  if(csize == 2)
    ansc++;
  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){
      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 (stderr)

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: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25