Submission #387916

#	Time	Username	Problem	Language	Result	Execution time	Memory
387916		kimbj0709	Love Polygon (BOI18_polygon)	C++14	54 / 100	743 ms	1048580 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<set<int> > adj(maxn);
vector<vector<int> > fadj(maxn);
vector<int> canuse(maxn,1);
map<string,int> map1;
int currcount = 0;
int ans = 0;
void dfs1(int node,int parent){
  for(auto k:fadj[node]){
    if(k!=parent&&canuse[k]==1){
      dfs1(k,node);
    }
  }
  if(canuse[node]==0){

  }
  else if(parent!=-1&&canuse[parent]==1){
    canuse[node] = 0;
    canuse[parent] = 0;
    ans++;
  }
  else{
    ans++;
    canuse[node] = 0;
  }
}
void dfs(int node){
  canuse[node] = 0;
  currcount++;
  for(auto k:fadj[node]){
    if(canuse[k]==1){
      dfs(k);
    }
  }
}
int mapper(string a){
  if(map1.count(a)==0){
    map1.insert({a,map1.size()});
  }
  return map1[a];
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n;
  string input1,input2;
  int a,b;
  cin >> n;
  if(n%2==1){
    cout << -1;
    return 0;
  }
  vector<int> indeg(maxn,0);
  for(int i=0;i<n;i++){
    cin >> input1 >> input2;
    a = mapper(input1);
    b = mapper(input2);
    if(a!=b){
      fadj[a].push_back(b);
      fadj[b].push_back(a);
      adj[a].insert(b);
      indeg[b]++;
    }
  }
  for(int i=0;i<n;i++){
    for(auto k:adj[i]){
      if(adj[k].find(i)!=adj[k].end()){
        canuse[i] = 0;
        canuse[k] = 0;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(canuse[i]==1&&indeg[i]==0){
      dfs1(i,-1);
    }
  }
  for(int i=0;i<n;i++){
    if(canuse[i]==1){
      dfs(i);
      if(currcount%2==1){
        ans += currcount/2+1;
      }
      else{
        ans += currcount/2;
      }
      currcount = 0;
    }
  }
  cout << ans;
}

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