Submission #1127408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127408		Ludissey	Love Polygon (BOI18_polygon)	C++20	100 / 100	185 ms	9820 KiB

polygon

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
vector<int> deg;
int n; 

vector<int> neigh;
vector<int> visited;
queue<int> leefs;
int rst=0;

void dfs(int x){
    rst++;
    visited[x]=true;
    if(visited[neigh[x]]) {
        return;
    }
    visited[neigh[x]]=true;
    deg[neigh[neigh[x]]]--;
    if(deg[neigh[neigh[x]]]==0&&neigh[x]!=neigh[neigh[x]]) leefs.push(neigh[neigh[x]]);
}


int dfs2(int x){
    visited[x]=true;
    if(visited[neigh[x]]||x==neigh[x]) {
        return 1;
    }
    return dfs2(neigh[x])+1;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    neigh.resize(n);
    deg.resize(n);
    visited.resize(n);
    map<string,int> mp;
    int t=0;
    for (int i = 0; i < n; i++)
    {
        string sa; string b; cin >> sa >> b;
        if(mp.find(sa)==mp.end()){
             //cerr << sa << " " << t<< "\n";
             mp[sa]=t++;
        }
        if(mp.find(b)==mp.end()) {
            //cerr << b << " " << t <<"\n";
            mp[b]=t++;
        }
        neigh[mp[sa]]=mp[b];
        deg[mp[b]]++;
    }
    
    for (int i = 0; i < n; i++)  
    {
        if(deg[i]==0) leefs.push(i);
    }
    for (int i = 0; i < n; i++){
        if(neigh[i]!=i&&neigh[neigh[i]]==i){
            visited[neigh[i]]=true;
            visited[i]=true;
        }
    }  
    
    while(!leefs.empty())
    {
        int u=leefs.front(); leefs.pop();
        if(visited[u]) continue;
        dfs(u);
    }
    for (int i = 0; i < n; i++)  
    {
        if(!visited[i]) {
            rst+=(dfs2(i)+1)/2;
        }
    }
    if(n%2) cout << -1 << "\n";
    else cout << rst << "\n";

    return 0;
}

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