Submission #1026954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026954		12345678	Love Polygon (BOI18_polygon)	C++17	54 / 100	198 ms	30680 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, t, vs[nx], res, cnt, l[nx], c[nx], used[nx];
string su[nx], sv[nx];
map<string, int> mp;
vector<int> d[nx], cy[nx];

int dfs(int u, int rt)
{
    vs[u]=1;
    for (auto v:d[u]) if (v==rt||(!vs[v]&&dfs(v, rt))) return c[u]=cnt, cy[cnt].push_back(u), 1;
    return 0;
}

void dfstree(int u, int p)
{
    for (auto v:d[u]) if (c[v]==-1) dfstree(v, u);
    if (u!=p&&!used[u]&&!used[p]) res++, used[u]=used[p]=1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>su[i]>>sv[i], mp[su[i]]=i, c[i]=-1;
    if (n%2) return cout<<-1, 0;
    for (int i=1; i<=n; i++) 
    {
        l[mp[su[i]]]=mp[sv[i]];
        if (mp[su[i]]!=mp[sv[i]]) d[mp[sv[i]]].push_back(mp[su[i]]);
        else cy[cnt++].push_back(i);
    }
    for (int i=1; i<=n; i++) if (!vs[i]&&dfs(i, i)) cnt++;
    for (int i=0; i<cnt; i++) 
    {
        int cnt=0;
        for (auto x:cy[i]) dfstree(x, x), cnt+=(!used[x]);
        //for (auto x:cy[i]) cout<<"debug "<<x<<' '<<used[x]<<'\n';
        //cout<<"count "<<cnt<<'\n';
        if (cnt==cy[i].size())
        {
            if (cy[i].size()==2) res+=2;
            else res+=cy[i].size()/2; 
        }
        for (auto x:cy[i])
        {
            if (used[x]&&!used[l[x]])
            {
                int tmp=l[x], sz=1;
                while (!used[l[tmp]]) sz++, tmp=l[tmp];
                res+=sz/2;
            }
        }
    }
    cout<<n-res;
}

/*
8
a b
b c
c a
d a
e f
f e
g h
h g

10
a b
b b
c d
d e
e e
f g
g h
h h
x x
y y

8
a b
b c
c d
d a
e a
f b
g c
h d

12
a b
b c
c d
d a
e a
f b
g c
h d
x e
y f
m m
n n
*/

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (cnt==cy[i].size())
      |             ~~~^~~~~~~~~~~~~~

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