oj.uz

Submission #446501

# Submission time Handle Problem Language Result Execution time Memory
446501 2021-07-22T08:09:17 Z prvocislo Love Polygon (BOI18_polygon) C++17
29 / 100
 2000 ms 12136 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if (n%2)
    {
        cout << "-1" << endl;
        return 0; 
    }
    map<string, int> m;
    vector<int> il(n, -1), lm(n, 0), happy(n, 0); // koho ja lubim, kolko postav lubi mna?
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        string a, b;
        cin >> a >> b;
        if (!m.count(a)) m[a] = cnt++;
        if (!m.count(b)) m[b] = cnt++;
        int ia = m[a], ib = m[b];
        il[ia] = ib, lm[ib]++;
        if (ia != ib && il[ib] == ia) happy[ia] = happy[ib] = true;
    }
    vector<int> stk;
    for (int i = 0; i < n; i++)
        if (lm[i] == 0) stk.push_back(i);
    int ans = 0, alone = 0;
    while (!stk.empty())
    {
        int i = stk.back(); stk.pop_back();
        if (happy[il[i]])
        {
            alone++;
            happy[i] = true;
            continue;
        }
        happy[i] = happy[il[i]] = true;
        ans++;
        if (!happy[il[il[i]]])
        {
            lm[il[il[i]]]--;
            if (!lm[il[il[i]]]) stk.push_back(il[il[i]]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (happy[i]) continue;
        int j = il[i], len = 1;
        while (j != i) happy[j] = true, len++, j = il[i];
        ans += (len>>1), alone += (len&1);
    }
    cout << ans+alone << "\n";
    return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Execution timed out 2076 ms 204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 2072 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 11604 KB Output is correct
2 Correct 227 ms 11500 KB Output is correct
3 Correct 235 ms 11464 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 210 ms 11384 KB Output is correct
6 Correct 219 ms 11856 KB Output is correct
7 Correct 239 ms 11844 KB Output is correct
8 Correct 194 ms 11896 KB Output is correct
9 Correct 198 ms 12136 KB Output is correct
10 Correct 163 ms 12104 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Execution timed out 2076 ms 204 KB Time limit exceeded
8 Halted 0 ms 0 KB -