Submission #369891

#TimeUsernameProblemLanguageResultExecution timeMemory
369891ivan_tudorLove Polygon (BOI18_polygon)C++14
29 / 100
451 ms24940 KiB
#include<bits/stdc++.h> using namespace std; const int N = 100005; map<string, int> id; set<pair<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})) continue; if(x != y){ gr[x].push_back(y); gr[y].push_back(x); } edges.insert({x, y}); } 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++){
      |               ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...