oj.uz

Submission #391684

# Submission time Handle Problem Language Result Execution time Memory
391684 2021-04-19T14:27:28 Z Victor Love Polygon (BOI18_polygon) C++17
29 / 100
 324 ms 33672 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(a, x) for (auto& a : x)
#define sz(a) a.size()
#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

umap<string, string> out;
umap<string, int> in;
uset<string> unloved;

int ans = 0, n;

void remove(string name) {
    if (in.count(out[name]) && 1 == in[out[name]]--) unloved.insert(out[name]);
    out.erase(name);
    in.erase(name);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    if (n & 1) {
        cout << -1 << endl;
        return 0;
    }

    string n1, n2;
    vector<string>arr(n*2);
    rep(i, 0, n) {
        cin >> arr[i] >> arr[i + n];
        out.emplace(arr[i], arr[i + n]);
        in.emplace(arr[i],0);
    }

    cout<<endl;
    vector<string> rem;
    rep(i, 0, n) {
        n1 = arr[i];
        n2 = arr[i + n];
        if(n1==n2)continue;
        if (out[n2] == n1) rem.push_back(n1);
        ++in[n2];
    }

    trav(name, rem) {
        out.erase(name);
        in.erase(name);
    }

    trav(person,in)if(!person.second)unloved.insert(person.first);

    while (!unloved.empty()) {
        string name = *unloved.begin();
        unloved.erase(unloved.begin());

        if (!out.count(name) || !out.count(out[name])) continue;

        ++ans;
        remove(out[name]);
        out.erase(name);
        in.erase(name);
    }
    
    cout << ans+sz(in) << endl;
}

Subtask #1
0 / 21.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 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
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 268 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 26024 KB Output is correct
2 Correct 262 ms 27400 KB Output is correct
3 Correct 202 ms 33672 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 234 ms 26252 KB Output is correct
6 Correct 263 ms 29976 KB Output is correct
7 Correct 324 ms 29892 KB Output is correct
8 Correct 234 ms 31780 KB Output is correct
9 Correct 238 ms 31856 KB Output is correct
10 Correct 212 ms 33628 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -