oj.uz

Submission #1026949

# Submission time Handle Problem Language Result Execution time Memory
1026949 2024-07-18T14:48:17 Z 12345678 Love Polygon (BOI18_polygon) C++17
54 / 100
 191 ms 32860 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; 
            continue;
        }
        for (auto x:cy[i])
        {
            if (used[x]&&!used[l[x]])
            {
                int tmp=x, sz=0;
                while (!used[l[tmp]]) sz++, tmp=l[tmp];
                res+=sz/2;
            }
        }
    }
    cout<<n-res;
}

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 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12732 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 3 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 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 188 ms 32012 KB Output is correct
5 Correct 178 ms 26664 KB Output is correct
6 Correct 181 ms 32860 KB Output is correct
7 Correct 55 ms 22624 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 22952 KB Output is correct
2 Correct 187 ms 24796 KB Output is correct
3 Correct 132 ms 23892 KB Output is correct
4 Correct 44 ms 20560 KB Output is correct
5 Correct 172 ms 29592 KB Output is correct
6 Correct 182 ms 22220 KB Output is correct
7 Correct 191 ms 22224 KB Output is correct
8 Correct 135 ms 23336 KB Output is correct
9 Correct 159 ms 21860 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 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12732 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 3 ms 12892 KB Output isn't correct
9 Halted 0 ms 0 KB -