제출 #1236561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236561		angels	Love Polygon (BOI18_polygon)	C++20	0 / 100	194 ms	9320 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]=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(!vis[par])
        {
            sol+=(sz[par]/2);
            vis[par]=1;
            if(sz[par]%2==1)
                sol++;
        }
    }
    cout<<sol;
    

    return 0;
}

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