Submission #952433

#	Time	Username	Problem	Language	Result	Execution time	Memory
952433		Yell0	Love Polygon (BOI18_polygon)	C++17	100 / 100	131 ms	32664 KiB

polygon

#include <bits/stdc++.h>
 
using namespace std;
const int MN=1e5+2;
int N;
set<int> fromgr[MN];
int togr[MN];
bool vis[MN];
int dpst[MN], dpew[MN];

void dfs(int u, int root) {
  vis[u] = 1;
  if(fromgr[u].empty()) {
    dpst[u] = 1;
    dpew[u] = 0;
    return;
  }
  dpst[u] = 1e9;
  dpew[u] = 0;
  for(int v : fromgr[u]) {
    if(v == root) continue;
    dfs(v, root);
    dpew[u] += dpst[v];
  }
  for(int v : fromgr[u]) {
    if(v == root) continue;
    dpst[u] = min(dpst[u], dpew[u] - dpst[v] + dpew[v] + 1);
  }
  if(dpst[u] == (int)1e9) dpst[u] = 1;
}

int solve(int u) {
  vector<bool> seen(N, 0);
  // find root
  seen[u] = 1;
  while(!seen[togr[u]]) {
    u = togr[u];
    seen[u] = 1;
  }
  // relationship
  if(togr[u] != u && togr[togr[u]] == u) {
    dfs(u, togr[u]);
    dfs(togr[u], u);
    return dpew[u] + dpew[togr[u]];
  }

  dfs(u, u);
  int ans = min(dpst[u], dpew[u] + 1);

  fromgr[togr[togr[u]]].erase(togr[u]);
  dfs(u, u);
  return min(ans, dpew[u] + dpew[togr[u]] + 1);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>N;
  if(N%2) {
    cout<<"-1\n";
    return 0;
  }
  unordered_map<string, int> id;
  vector<string> pts;
  for(int i=0; i<N; ++i) {
    string a,b;
    cin>>a>>b;
    id[a] = i;
    pts.emplace_back(b);
  }
  for(int i=0; i<N; ++i) {
    togr[i] = id[pts[i]];
    fromgr[id[pts[i]]].emplace(i);
  }

  int ans = 0;
  for(int i=0; i<N; ++i) {
    if(vis[i]) continue;
    ans += solve(i);
  }
  // for(int i=0; i<N; ++i) cout<<dpst[i]<<' '<<dpew[i]<<'\n';
  cout<<ans<<'\n';
  return 0;
}

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