Submission #1027121

#TimeUsernameProblemLanguageResultExecution timeMemory
102712112345678Love Polygon (BOI18_polygon)C++17
100 / 100
205 ms32984 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5; int n, t, vs[nx], res, cnt, l[nx], c[nx], used[nx]; string su[nx], sv[nx]; map<string, int> mp; vector<int> d[nx], cy[nx]; int dfs(int u, int rt) { vs[u]=1; for (auto v:d[u]) if (v==rt||(!vs[v]&&dfs(v, rt))) return c[u]=cnt, cy[cnt].push_back(u), 1; return 0; } void dfstree(int u, int p) { for (auto v:d[u]) if (c[v]==-1) dfstree(v, u); if (u!=p&&!used[u]&&!used[p]) res++, used[u]=used[p]=1; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n; for (int i=1; i<=n; i++) cin>>su[i]>>sv[i], mp[su[i]]=i, c[i]=-1; if (n%2) return cout<<-1, 0; for (int i=1; i<=n; i++) { l[mp[su[i]]]=mp[sv[i]]; if (mp[su[i]]!=mp[sv[i]]) d[mp[sv[i]]].push_back(mp[su[i]]); else cy[cnt++].push_back(i); } for (int i=1; i<=n; i++) if (!vs[i]&&dfs(i, i)) cnt++; for (int i=0; i<cnt; i++) { if (cy[i].size()==2) res+=2, used[cy[i][0]]=used[cy[i][1]]=1; int cnt=0; for (auto x:cy[i]) dfstree(x, x), cnt+=(!used[x]); if (cnt==cy[i].size()) { if (cy[i].size()==2) res+=2; else res+=cy[i].size()/2; } for (auto x:cy[i]) { if (used[x]&&!used[l[x]]) { int tmp=l[x], sz=1; while (!used[l[tmp]]) sz++, tmp=l[tmp]; res+=sz/2; } } } cout<<n-res; }

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (cnt==cy[i].size())
      |             ~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...