Submission #1239232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239232		angels	Love Polygon (BOI18_polygon)	C++20	100 / 100	177 ms	9508 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    map<string, int>str_to_int;
    int graph[n];
    int index=0;
    string aa, bb;
    int in_degree[n];
    memset(graph, -1, sizeof(graph));
    memset(in_degree, 0, sizeof(in_degree));
    for(int i=0; i<n; i++)
    {
        cin>>aa>>bb;
        if(str_to_int.find(aa)==str_to_int.end())
            str_to_int[aa]=index++;
        if(str_to_int.find(bb)==str_to_int.end())
            str_to_int[bb]=index++;
        graph[str_to_int[aa]]=str_to_int[bb];
        in_degree[str_to_int[bb]]++;
    }
    
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    
    bool visited[n];
    memset(visited, 0, sizeof(visited));
    queue<int>q;
    int node;
    for(int i=0; i<n; i++)
    {
        if(visited[i]==0 && i==graph[graph[i]] && graph[i]!=i)
        {
            visited[i]=1;
            visited[graph[i]]=1;
        }
        else if(visited[i]==0 && in_degree[i]==0)
        {
            q.push(i);
        }
    }
    int rez=0;
    while(!q.empty())
    {
        node=q.front();
        q.pop();
        if(!visited[graph[node]])
        {
            rez++;
            in_degree[node]++;
            visited[node]=1;
            visited[graph[node]]=1;
            in_degree[graph[graph[node]]]--;
            if(in_degree[graph[graph[node]]]==0)
            {
                q.push(graph[graph[node]]);
            }
        }
        else
        {
            in_degree[graph[node]]--;
            graph[node]=node;
            in_degree[node]++;
        }
    }
    int sz;
    for(int i=0; i<n; i++)
    {
        if(!visited[i] && graph[i]==i)
        {
            rez++;
            visited[i]=1;
        }
        else if(!visited[i])
        {
            node=i, sz=0;
            while(visited[node]==0)
            {
                visited[node]=1;
                node=graph[node];
                sz++;
            }
            rez+=(sz+1)/2;
        }
    }
    cout<<rez;
    

    return 0;
}

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