Submission #1236684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236684		angels	Love Polygon (BOI18_polygon)	C++20	54 / 100	240 ms	22064 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);
}
bool tc_2=0;
void Union(int a, int b, int p[], int sz[])
{
    a=Find(a, p);
    b=Find(b, p);
    if(a==b)
    {
        tc_2=1;
        return;
    }
    if(sz[a]<sz[b])
        swap(a, b);
    sz[a]+=sz[b];
    p[b]=p[a];
}
long long rez=0;
void dfs1(vector<int>graph[], int node, int parent, bool visited[])
{
    for(int i=0; i<graph[node].size(); i++)
    {
        if(graph[node][i]!=parent)
            dfs1(graph, graph[node][i], node, visited);
    }
    if(visited[node]==0 && visited[parent]==0)
    {
        visited[node]=1;
        visited[parent]=1;
        rez++;
    }
    if(visited[node]==0 && visited[parent]==1)
    {
        visited[node]=1;
        rez++;
    }
}

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);
    memset(graph, -1, sizeof(graph));
    vector<int>graph_inverse[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];
        if(aa!=bb)
            Union(str_to_int[aa], str_to_int[bb], p, sz);
        graph_inverse[str_to_int[bb]].push_back(str_to_int[aa]);
    }
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    if(tc_2)
    {
        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;
    }
    else
    {
        bool visited[n];
        memset(visited, 0, sizeof(visited));
        for(int i=0; i<n; i++)
        {
            if(graph[i]==-1)
            {
                cout<<-1;
                return 0;
            }
            if(graph[i]!=i && graph[graph[i]]==i)
            {
                visited[i]=1;
                visited[graph[i]]=1;
            }
        }
        for(int i=0; i<n; i++)
        {
            if(graph[i]==i && visited[i]==0)
            {
                dfs1(graph_inverse, i, i, visited);
            }
        }
        cout<<rez;
    }
    

    return 0;
}

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