Submission #1236579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236579		angels	Love Polygon (BOI18_polygon)	C++20	0 / 100	184 ms	9036 KiB

polygon

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

void dfs(int node, int graph[], int &sz, bool vis[])
{
    if(vis[node])
        return;
    vis[node]=1;
    sz++;
    dfs(graph[node], graph, sz, vis);
}

int main()
{
    int n;
    cin>>n;
    map<string, int>str_to_int;
    int N=2e5+1;
    int graph[N];
    int index=0;
    string aa, bb;
    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;
            index++;
        }
        if(str_to_int.find(bb)==str_to_int.end())
        {
            str_to_int[bb]=index;
            index++;
        }
        graph[str_to_int[aa]]=str_to_int[bb];
    }
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    bool vis[N];
    memset(vis, 0, sizeof(vis));
    long long int sol=0;
    int sz=1;
    for(int i=0; i<index; i++)
    {
        if(!vis[i])
        {
            sz=0;
            dfs(i, graph, sz, vis);
            sol+=(sz/2);
            if(sz%2==1)
                sol++;
        }
    }
    cout<<sol;
    

    return 0;
}

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