Submission #1272201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272201		Davdav1232	Love Polygon (BOI18_polygon)	C++20	100 / 100	205 ms	22008 KiB

polygon

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int num_pairs=0;
int num_paired=0;
vector<int> last_vis;
vector<bool> is_polygon;
vector<bool> taken;
vvi G;

void dfs_pair(int node, int par){
    for(int neighbor : G[node]){
        if(neighbor==par) continue;
        dfs_pair(neighbor, node);
    }
    if(par==node) return;
    if(!taken[par] && !taken[node]){
        num_paired++;
        taken[par]=1;
        taken[node]=1;
    }
}
int main() {
	int n; cin>>n;
	if(n%2==1){
        cout<<-1;
        return 0;
    }
    //need to get the input
    vector<string> names(n);
    
    map<string, int> func;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        func[s]=i;
        cin>>s;
        
        names[i]=s;
        
    }
    vi loves(n);
    for(int i=0; i<n; i++){
        loves[i]=func[names[i]];
    }
    //found the thing
    last_vis.assign(n, -1);
    is_polygon.assign(n, 0);
    taken.assign(n, 0);
    for(int i=0; i<n; i++){
        last_vis[i]=i;
        int curr=loves[i];
        while(last_vis[curr]==-1){
            last_vis[curr]=i;
            curr=loves[curr];
        }
        if(last_vis[curr]==i){
            //we have a polygon starting with curr
            int l=0;
            while(is_polygon[curr]==0){
                is_polygon[curr]=1;
                curr=loves[curr];
                l++;
            }
            if(l==2){
                num_pairs++;
                taken[curr]=1;
                taken[loves[curr]]=1;
            }
        }
        else continue;
    }
    G.resize(n);
    for(int i=0; i<n; i++){
        if(is_polygon[i]) continue;
        G[i].push_back(loves[i]);
        G[loves[i]].push_back(i);
        //graph
    }
    //found all polygons. now time to root from all of them and do dp
    for(int i=0; i<n; i++){
        if(is_polygon[i]){
            dfs_pair(i, i);
        }
    }
    vector<bool> vis(n, 0);
    for(int i=0; i<n; i++){
        if(!is_polygon[i] || vis[i]) continue;
        int curr=i;
        int l=0;
        while(true){
            if(taken[curr]){
                //we know what to do here
                //start the loop from here and count the lengths of the free segments
                int start=curr;
                l=0;
                curr=loves[curr];
                vis[start]=1;
                vis[curr]=1;
                while(curr!=start){
                    if(taken[curr]){
                        num_paired+=l/2;
                        l=0;
                    }
                    else l++;
                    vis[curr]=1;
                    curr=loves[curr];
                }

                num_paired+=l/2;
                break;
            }
            else{
                if(vis[curr]){
                    num_paired+=l/2;
                    break;
                }
                l++;
                vis[curr]=1;
                curr=loves[curr];
            }
        }
    }
    //just need to find a way to pair the polygons themselves

    cout<<n-num_paired-2*num_pairs;
    return 0;
}

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