oj.uz

Submission #1026954

# Submission time Handle Problem Language Result Execution time Memory
1026954 2024-07-18T15:02:47 Z 12345678 Love Polygon (BOI18_polygon) C++17
54 / 100
 198 ms 30680 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12900 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Incorrect 2 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 198 ms 29972 KB Output is correct
5 Correct 193 ms 24484 KB Output is correct
6 Correct 188 ms 30680 KB Output is correct
7 Correct 47 ms 20560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 23132 KB Output is correct
2 Correct 186 ms 24776 KB Output is correct
3 Correct 131 ms 23888 KB Output is correct
4 Correct 49 ms 20628 KB Output is correct
5 Correct 182 ms 29524 KB Output is correct
6 Correct 183 ms 22228 KB Output is correct
7 Correct 181 ms 22352 KB Output is correct
8 Correct 162 ms 23356 KB Output is correct
9 Correct 171 ms 21804 KB Output is correct
10 Correct 135 ms 21204 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12900 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Incorrect 2 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -