oj.uz

Submission #497676

# Submission time Handle Problem Language Result Execution time Memory
497676 2021-12-23T14:36:34 Z LittleCube Love Polygon (BOI18_polygon) C++14
25 / 100
 282 ms 31592 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, idx, pre[100005], vis[100005], visr[100005], deg[100005], ans;
bool used[100005];
map<string, int> mp;
vector<int> E[100005], rE[100005], newE[100005];
vector<pii> oE;
void dfs(int k, int r)
{
    for (int i : E[k])
        if (!vis[i] || (visr[i] == r && vis[i] == 1))
        {
            vis[i]++;
            visr[i] = r;
            dfs(i, r);
        }
}

void tree_matching(int k)
{
    for (int i : rE[k])
        if (vis[i] != 2)
            tree_matching(i);
    for (int i : rE[k])
        if (vis[i] != 2 && !used[i])
        {
            used[k] = used[i] = 1;
            ans++;
            break;
        }
}

void tree_matching2(int k)
{
    vis[k] = 3;
    for (int i : newE[k])
        if (vis[i] != 3 && !used[i])
            tree_matching2(i);
    for (int i : newE[k])
        if (!used[i])
        {
            used[k] = used[i] = 1;
            ans++;
            break;
        }
    vis[k] = 0;
}

#define debug(arr)               \
    for (int i = 1; i <= N; i++) \
        cout << arr[i] << " \n"[i == N];

signed main()
{
    cin >> N;
    if (N % 2 == 1)
    {
        cout << -1 << '\n';
        return 0;
    }
    for (int i = 1; i <= N; i++)
    {
        string s, t;
        cin >> s >> t;
        if (mp[s] == 0)
            mp[s] = ++idx;
        if (mp[t] == 0)
            mp[t] = ++idx;
        oE.emplace_back(make_pair(mp[s], mp[t]));
    }
    //for (auto p : mp)
    //    cout << p.F << " " << p.S << '\n';

    sort(oE.begin(), oE.end(), [](pii p1, pii p2)
         { return pii{min(p1.F, p1.S), max(p1.F, p1.S)} < pii{min(p2.F, p2.S), max(p2.F, p2.S)}; });
    for (int i = 1; i < N; i++)
        if (oE[i].F == oE[i - 1].S && oE[i].S == oE[i - 1].F)
            used[oE[i].F] = used[oE[i].S] = 1;

    //cout << "pair ";
    //debug(used);

    for (pii p : oE)
        if (!used[p.F])
        {
            int u = p.F, v = (used[p.S] ? p.F : p.S);
            E[u].emplace_back(v);
            rE[v].emplace_back(u);
        }
    mp.clear();
    for (int i = 1; i <= N; i++)
        if (!vis[i])
        {
            vis[i] = 1;
            dfs(i, i);
        }

    //cout << "vis ";
    //debug(vis);

    for (int i = 1; i <= N; i++)
        if (vis[i] == 2)
        {
            tree_matching(i);
            //cout << "firstTree ";
            //debug(used);
        }

    for (int i = 1; i <= N; i++)
        if (!used[i])
            for (int j : E[i])
                if (!used[j])
                    newE[i].emplace_back(j);
    for (int i = 1; i <= N; i++)
        if (!used[i])
            tree_matching2(i);

    //cout << "secondChain ";
    //debug(used);

    for (int i = 1; i <= N; i++)
        if (!used[i])
            ans++;
    cout << ans << '\n';
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 4 ms 7352 KB Output is correct
3 Correct 4 ms 7348 KB Output is correct
4 Correct 4 ms 7248 KB Output is correct
5 Correct 4 ms 7356 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7348 KB Output is correct
8 Correct 4 ms 7344 KB Output is correct
9 Correct 4 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Correct 3 ms 7352 KB Output is correct
12 Incorrect 3 ms 7248 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 3 ms 7244 KB Output is correct
4 Correct 274 ms 28536 KB Output is correct
5 Correct 273 ms 24876 KB Output is correct
6 Correct 282 ms 31592 KB Output is correct
7 Correct 4 ms 7364 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 4 ms 7352 KB Output is correct
3 Correct 4 ms 7348 KB Output is correct
4 Correct 4 ms 7248 KB Output is correct
5 Correct 4 ms 7356 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7348 KB Output is correct
8 Correct 4 ms 7344 KB Output is correct
9 Correct 4 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Correct 3 ms 7352 KB Output is correct
12 Incorrect 3 ms 7248 KB Output isn't correct
13 Halted 0 ms 0 KB -