Submission #486738

#	Time	Username	Problem	Language	Result	Execution time	Memory
486738		FatihSolak	Love Polygon (BOI18_polygon)	C++17	100 / 100	303 ms	24732 KiB

polygon

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
int ans = 0;
int edge[N];
bool cycle[N];
int vis[N];
bool del[N];
int root[N];
void dfs(int v){
    //cout << v << " " << endl;
    vis[v] = 1;
    if(vis[edge[v]] == 1){
        cycle[v] = 1;
        int tmp = edge[v];
        while(tmp != v){
            cycle[tmp] = 1;
            tmp = edge[tmp];
        }
    }
    else if(!vis[edge[v]] && !del[edge[v]]){
        dfs(edge[v]);
    }
    else if(del[edge[v]]){
        cycle[v] = 1;
    }
    vis[v] = 2;
}
void dfs2(int v){
    for(auto u:adj[v]){
        if(cycle[u] || del[u])continue;
        dfs2(u);
        ans += !del[u];
        if(!del[u]){
            del[v] = del[u] = 1;
        }
    }
}
void solve(){
    int n;
    cin >> n;
    int cnt = 1;
    map<string,int>val;
    for(int i=1;i<=n;i++){
        string s,t;
        cin >> s >> t;
        if(!val[s])val[s] = cnt++;
        if(!val[t])val[t] = cnt++;
        edge[val[s]] = val[t];
        if(edge[val[t]] == val[s] && s != t){
            del[val[s]] = 1;
            del[val[t]] = 1;
        }
        else adj[val[t]].push_back(val[s]);
    }
    if(n%2){
        cout << -1 << endl;
        return;
    }
    /*
    for(auto u:val){
        cout << u.first << " "<<u.second << " " << del[u.second] << endl;
    }*/
    for(int i=1;i<=n;i++){
        if(!vis[i] && !del[i]){
            //cout << i << " asdas" << endl;
            dfs(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " "<<u.second << " " << cycle[u.second] << endl;
    }*/
    for(int i=1;i<=n;i++){
        if(cycle[i] && !del[i]){
            dfs2(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(del[i])continue;
        vector<int> v;
        int tmp = i;
        while(v.empty() || tmp != i){
            v.push_back(tmp);
            if(!del[edge[tmp]])
                tmp = edge[tmp];
            else {
                tmp = -1;
                break;
            }
        }
        if(tmp == i){
            if(v.size() != 2){
                ans += v.size()/2 + v.size()%2;
            }
            for(auto u:v)del[u] = 1;
            continue;
        }
        int bef = -1;
        for(auto u:adj[i]){
            if(!del[u])bef = u;
        }
        while(bef != -1){
            v.push_back(bef);
            for(auto u:adj[bef]){
                if(!del[u]){
                    bef = u;
                    break;
                }
            }
            if(bef == v.back())bef = -1;
        }
        for(auto u:v)del[u] = 1;
        ans += v.size()/2 + v.size()%2;
    }
    cout << ans;

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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