Submission #862285

#	Time	Username	Problem	Language	Result	Execution time	Memory
862285		guagua0407	Love Polygon (BOI18_polygon)	C++17	25 / 100	223 ms	31408 KiB

polygon

/*
燒雞
 燒雞
  燒雞    好想進選訓
 燒雞
燒雞
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
 
const int mxn=1e5+5;
map<string,string> mp;
map<string,int> rev;
vector<string> convert(mxn);
vector<int> adj(mxn);
vector<int> adjr[mxn];
vector<bool> visited(mxn,false);
vector<bool> used(mxn,false);
vector<bool> isnode(mxn,false);
vector<int> szs;
 
void dfs(int v){
    visited[v]=true;
    for(auto u:adjr[v]){
        if(visited[u]) continue;
        if(used[u]==false and used[v]==false){
            used[u]=true;
            used[v]=true;
        }
        dfs(u);
    }
}
 
void dfs2(int v,int cnt=1){
    visited[v]=true;
    if(visited[adj[v]]==true){
        szs.push_back(cnt);
        return;
    }
    else{
        dfs2(adj[v],cnt+1);
    }
}
 
int main() {_
    //setIO("wayne");
    int n;
    cin>>n;
    if(n&1){
        cout<<-1;
        return 0;
    }
    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
        mp[a]=b;
    }
    int cnt=0;
    for(auto &v:mp){
        rev[v.f]=cnt;
        //cout<<v.f<<' '<<cnt<<'\n';
        cnt++;
    }
    for(auto &v:mp){
        adj[rev[v.f]]=rev[v.s];
        adjr[rev[v.s]].push_back(rev[v.f]);
    }
    bool ok=true;
    for(int i=0;i<n;i++){
        if(adjr[i].size()==0){
            ok=false;
        }
    }
    if(ok==false){
        int ans=0;
        for(int i=0;i<n;i++){
            if(!visited[i] and adj[i]==i) dfs(i);
        }
        for(int i=0;i<n;i++){
            if(used[i]){
                //cout<<i<<'\n';
                ans++;
            }
        }
        //cout<<ans<<'\n';
        cout<<(ans/2+(n-ans));
    }
    else{
        for(int i=0;i<n;i++){
            if(!visited[i]) dfs2(i);
        }
        int ans=0;
        int cnt2=0;
        for(int v:szs){
            if(v==2) continue;
            if(v%2==0){
                ans+=(v/2);
            }
            else{
                ans+=(v/2);
                cnt2++;
            }
        }
        cout<<ans+cnt2;
    }
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

polygon.cpp: In function 'void setIO(std::string)':
polygon.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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