Submission #1010642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010642		alexdd	Love Polygon (BOI18_polygon)	C++17	100 / 100	147 ms	28528 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
int n,rez;
pair<string,string> cit[100005];
map<string,int> nrm;
vector<int> con[100005];
int nxt[100005];
bool visited[100005],vis2[100005];
bool iscyc[100005];


bool gata[100005];
void dfs(int nod)
{
    visited[nod]=vis2[nod]=1;
    for(auto adj:con[nod])
    {
        if(iscyc[adj])
            continue;
        dfs(adj);
        if(!gata[adj] && !gata[nod])
        {
            gata[adj]=gata[nod]=1;
            rez++;
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>cit[i].first>>cit[i].second;
        nrm[cit[i].first] = i;
    }
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        nxt[i] = nrm[cit[i].second];
        con[nrm[cit[i].second]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(visited[i])
            continue;
        int cur=i;
        while(1)
        {
            vis2[cur]=1;
            cur = nxt[cur];
            if(vis2[cur])
                break;
        }
        vector<int> cyc;
        int init = cur;
        while(1)
        {
            cyc.push_back(cur);
            iscyc[cur]=1;
            cur = nxt[cur];
            if(cur==init)
                break;
        }
        if((int)cyc.size()==2)
            gata[cyc[0]]=gata[cyc[1]]=1;
        bool bl=0;
        for(auto x:cyc)
        {
            dfs(x);
            if(gata[x]) bl=1;
        }
        if(!bl)
        {
            if((int)cyc.size()%2==0)
            {
                for(int i=0;i<cyc.size();i++)
                    gata[cyc[i]]=1;
                rez += (int)cyc.size()/2;
            }
            else
            {
                for(int i=1;i<cyc.size();i++)
                    gata[cyc[i]]=1;
                rez += (int)cyc.size()/2;
            }
        }
        else
        {
            for(int i=0;i<cyc.size();i++)
            {
                if(gata[cyc[i]])
                {
                    int poz = i-1;
                    if(i==0) poz = (int)cyc.size()-1;
                    while(1)
                    {
                        int poz1 = (poz-1 + (int)cyc.size())%(int)cyc.size();
                        if(gata[cyc[poz1]] || gata[cyc[poz]])
                            break;
                        //cout<<"scoate\n";
                        gata[cyc[poz]]=gata[cyc[poz1]]=1;
                        rez++;
                        poz = (poz1-1 + (int)cyc.size())%(int)cyc.size();
                    }
                }
            }
        }
    }
    int ramase=0;
    for(int i=1;i<=n;i++)
        if(!gata[i])
            ramase++;
    rez += ramase;
    cout<<rez;
    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for(int i=0;i<cyc.size();i++)
      |                             ~^~~~~~~~~~~
polygon.cpp:87:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                 for(int i=1;i<cyc.size();i++)
      |                             ~^~~~~~~~~~~
polygon.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int i=0;i<cyc.size();i++)
      |                         ~^~~~~~~~~~~

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