Submission #1236598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236598		angels	Love Polygon (BOI18_polygon)	C++20	25 / 100	246 ms	9460 KiB

polygon

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

void make_set(int p[], int sz[], int n)
{
    for(int i=0; i<n; i++)
    {
        p[i]=i;
        sz[i]=1;
    }
}

int Find(int i, int p[])
{
    if(i==p[i])
        return p[i];
    return p[i]=Find(p[i], p);
}

void Union(int a, int b, int p[], int sz[])
{
    a=Find(a, p);
    b=Find(b, p);
    if(a==b)
        return;
    if(sz[a]<sz[b])
        swap(a, b);
    sz[a]+=sz[b];
    p[b]=p[a];
}

int main()
{
    int n;
    cin>>n;
    map<string, int>str_to_int;
    int graph[n];
    int index=0;
    string aa, bb;
    int p[n], sz[n];
    make_set(p, sz, n);
    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];
        Union(str_to_int[aa], str_to_int[bb], p, sz);
    }
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    bool vis[n];
    memset(vis, 0, sizeof(vis));
    int par;
    long long int sol=0;
    for(int i=0; i<n; i++)
    {
        par=Find(i, p);
        if(sz[par]==2)
            continue;
        if(!vis[par])
        {
            sol+=(sz[par]+1)/2;
            vis[par]=1;
        }
    }
    cout<<sol;
    

    return 0;
}

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