Submission #787067

#	Time	Username	Problem	Language	Result	Execution time	Memory
787067		Yell0	Love Polygon (BOI18_polygon)	C++17	25 / 100	120 ms	16988 KiB

polygon

#include <bits/stdc++.h>

using namespace std;
const int MN=1e5+2;
int N,pa[MN],ans=0;
vector<pair<string,string>> edges;
map<string,int> mp;
bool vis[MN];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N;
  if(N%2) {
    cout<<"-1\n";
    return 0;
  }
  for(int i=1;i<=N;++i) {
    pair<string,string> p;
    cin>>p.first>>p.second;
    mp[p.first]=i;
    edges.push_back(p);
  }
  for(int i=0;i<N;++i) pa[mp[edges[i].first]]=mp[edges[i].second];

  for(int u=1;u<=N;++u) {
    if(vis[u]) continue;
    int v=u,sz=0;
    while(!vis[v]) {
      vis[v]=1;
      ++sz;
      v=pa[v];
    }
    if(sz==2) continue;
    ans+=sz/2+sz%2;
  }
  cout<<ans<<'\n';
  return 0;
}

• Subtask 1: 0 / 21
• Subtask 2: 25 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25