oj.uz

Submission #497679

# Submission time Handle Problem Language Result Execution time Memory
497679 2021-12-23T14:48:54 Z LittleCube Love Polygon (BOI18_polygon) C++14
29 / 100
 360 ms 29460 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;
        }
}

#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 (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;
            visr[i] = i;
            dfs(i, i);
        }

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

    for (int i = 1; i <= N; i++)
        if (vis[i] == 2)
            tree_matching(i);

    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 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 3 ms 7244 KB Output is correct
4 Incorrect 3 ms 7244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 22288 KB Output is correct
2 Correct 274 ms 25680 KB Output is correct
3 Correct 245 ms 25148 KB Output is correct
4 Correct 3 ms 7364 KB Output is correct
5 Correct 339 ms 29460 KB Output is correct
6 Correct 317 ms 23716 KB Output is correct
7 Correct 245 ms 23920 KB Output is correct
8 Correct 339 ms 24064 KB Output is correct
9 Correct 247 ms 23176 KB Output is correct
10 Correct 210 ms 22324 KB Output is correct
11 Correct 5 ms 7248 KB Output is correct
12 Correct 4 ms 7248 KB Output is correct
13 Correct 4 ms 7248 KB Output is correct
14 Correct 6 ms 7248 KB Output is correct

Subtask #4
0 / 25.0

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