oj.uz

Submission #895698

# Submission time Handle Problem Language Result Execution time Memory
895698 2023-12-30T14:44:19 Z krizsu222 Love Polygon (BOI18_polygon) C++17
0 / 100
 197 ms 20308 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+2;

int n, out[maxn], actnr, ilpoj, res;
string name1, name2;
set <int> in[maxn];
map <string, int> nr;
queue <int> q;
bool done[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    
    for(int i=1; i<=n; i++)
    {
        cin >> name1 >> name2;
        if(!nr[name1]) nr[name1] = ++actnr;
        // cout << name1 << ": " << nr[name1] << '\n';
        if(!nr[name2]) nr[name2] = ++actnr;
        // cout << name2 << ": " << nr[name2] << '\n';
        out[nr[name1]] = nr[name2];
        in[nr[name2]].insert(nr[name1]);
    }

    if(n&1)
    {
        cout << "-1\n";
        return 0;
    }

    for(int i=1; i<=n; i++)
    {
        if(out[i] == i) ilpoj++, done[i] = 1;
        else if(out[out[i]] == i) done[i] = done[out[i]] = 1;
        else if(!in[i].size()) q.push(i);
    }

    while(!q.empty())
    {
        int v = q.front(); q.pop();
        if(done[out[v]]) ilpoj++, done[v] = 1;
        else
        {
            int u = out[v];
            in[out[u]].erase(u);
            if(!in[out[u]].size()) q.push(out[u]);
            done[v] = done[u] = 1; res++;
        }
    }

    for(int i=1; i<=n; i++)
    {
        if(done[i]) continue;
        int v = i, act = 0;
        while(out[v] != i) act++, v = out[v];
        ilpoj += (act&1); res += (act/2);
    }

    cout << res+ilpoj << '\n';
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 1 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 20308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -