oj.uz

Submission #1054883

# Submission time Handle Problem Language Result Execution time Memory
1054883 2024-08-12T12:51:58 Z Zicrus Fountain Parks (IOI21_parks) C++17
15 / 100
 626 ms 207300 KB 
#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
 
typedef long long ll;
 
ll n;
 
vector<ll> lnk;
vector<ll> sz;
 
ll find(ll a) {
    if (a != lnk[a]) lnk[a] = find(lnk[a]);
    return lnk[a];
}
 
bool unite(ll a, ll b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (sz[a] > sz[b]) swap(a, b);
    lnk[a] = b;
    sz[b] += sz[a];
    return true;
}
 
int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    mt19937 mt(743);
    vector<pair<pair<ll, ll>, ll>> coords(n);
    for (int i = 0; i < n; i++) coords[i] = {{x[i], y[i]}, i};
    shuffle(coords.begin(), coords.end(), mt);
    for (int i = 0; i < n; i++) {
        x[i] = coords[i].first.first;
        y[i] = coords[i].first.second;
    }
    lnk = vector<ll>(n);
    sz = vector<ll>(n, 1);
    for (int i = 0; i < n; i++) lnk[i] = i;
    unordered_map<ll, ll> pts;
    vector<pair<ll, ll>> edges;
    unordered_set<ll> hasEdge;
    for (int i = 0; i < n; i++) {
        ll hash = ((ll)x[i] << 31) | (ll)y[i];
        pts[hash] = i;
    }
    for (ll i = 0; i < n; i++) {
        ll hashL = (((ll)x[i]-2) << 31) | ((ll)y[i]);
        if (pts.count(hashL)) {
            ll hash = (min(i, pts[hashL]) << 31) | max(i, pts[hashL]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashL]});
                hasEdge.insert(hash);
            }
        }
        ll hashR = (((ll)x[i]+2) << 31) | ((ll)y[i]);
        if (pts.count(hashR)) {
            ll hash = (min(i, pts[hashR]) << 31) | max(i, pts[hashR]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashR]});
                hasEdge.insert(hash);
            }
        }
        ll hashD = (((ll)x[i]) << 31) | ((ll)y[i]-2);
        if (pts.count(hashD)) {
            ll hash = (min(i, pts[hashD]) << 31) | max(i, pts[hashD]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashD]});
                hasEdge.insert(hash);
            }
        }
        ll hashU = (((ll)x[i]) << 31) | ((ll)y[i]+2);
        if (pts.count(hashU)) {
            ll hash = (min(i, pts[hashU]) << 31) | max(i, pts[hashU]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashU]});
                hasEdge.insert(hash);
            }
        }
    }
 
    unordered_map<ll, ll> poss;
    unordered_set<ll> twos;
    unordered_map<ll, ll> lnk, lnkU;
    vector<pair<ll, ll>> edgeHashes(edges.size());
    for (int i = 0; i < edges.size(); i++) {
        auto e = edges[i];
        ll midX = (x[e.first] + x[e.second]) / 2;
        ll midY = (y[e.first] + y[e.second]) / 2;
        ll leftX = midX - (midY - y[e.second]);
        ll leftY = midY + (midX - x[e.second]);
        ll rightX = midX + (midY - y[e.second]);
        ll rightY = midY - (midX - x[e.second]);
        ll hashL = (leftX << 31) | leftY;
        ll hashR = (rightX << 31) | rightY;
        if (poss[hashL] == 2) twos.erase(hashL);
        poss[hashL]++;
        if (poss[hashL] == 2) twos.insert(hashL);
        if (poss[hashR] == 2) twos.erase(hashR);
        poss[hashR]++;
        if (poss[hashR] == 2) twos.insert(hashR);
        lnk[hashL] ^= i;
        lnk[hashR] ^= i;
        lnkU[hashL] = i;
        lnkU[hashR] = i;
        edgeHashes[i] = {hashL, hashR};
    }
 
    vector<int> a(edges.size()), b(edges.size());
    queue<ll> q;
    for (auto &e : poss) {
        if (e.second != 1) continue;
        q.push(e.first);
    }
    ll cnt = 0;
    unordered_set<ll> used;
    while (cnt < edges.size()) {
        while (!q.empty()) {
            ll hash = q.front(); q.pop();
            if (poss[hash] != 1 || used.count(hash)) continue;
            cnt++;
            ll id = lnk[hash];
            a[id] = hash >> 31;
            b[id] = hash & ~(1 << 31);
            used.insert(id);
            if (--poss[edgeHashes[id].first] == 1) { q.push(edgeHashes[id].first); twos.erase(edgeHashes[id].first); }
            if (poss[edgeHashes[id].first] == 2) twos.insert(edgeHashes[id].first);
            if (--poss[edgeHashes[id].second] == 1) { q.push(edgeHashes[id].second); twos.erase(edgeHashes[id].second); }
            if (poss[edgeHashes[id].second] == 2) twos.insert(edgeHashes[id].second);
            lnk[edgeHashes[id].first] ^= id;
            lnk[edgeHashes[id].second] ^= id;
        }
        if (cnt < edges.size()) {
            ll v = *twos.begin();
            twos.erase(twos.begin());
            for (int i = 0; i < 1; i = 10) {
                i = lnkU[v];
                if (used.count(i)) continue;
                auto e = edges[i];
                ll midX = (x[e.first] + x[e.second]) / 2;
                ll midY = (y[e.first] + y[e.second]) / 2;
                if (abs(midX - (v >> 31)) + abs(midY - (v & ~(1 << 31))) > 1) continue;
                a[i] = v >> 31;
                b[i] = v & ~(1 << 31);
                poss[v] = 0;
                ll otherX = a[i] + 2 * (midX - a[i]);
                ll otherY = b[i] + 2 * (midY - b[i]);
                ll otherHash = (otherX << 31) | otherY;
                if (poss[otherHash] == 2) twos.erase(otherHash);
                poss[otherHash]--;
                if (poss[otherHash] == 2) twos.insert(otherHash);
                lnk[otherHash] ^= i;
                while (poss[otherHash == 1]) {
                    ll edge = lnk[otherHash];
                    auto e = edges[edge];
                    ll midX = (x[e.first] + x[e.second]) / 2;
                    ll midY = (y[e.first] + y[e.second]) / 2;
                    a[edge] = otherHash >> 31;
                    b[edge] = otherHash & ~(1 << 31);
                    ll otherX = a[edge] + 2 * (midX - a[edge]);
                    ll otherY = b[edge] + 2 * (midY - b[edge]);
                    otherHash = (otherX << 31) | otherY;
                    if (poss[otherHash] == 2) twos.erase(otherHash);
                    poss[otherHash]--;
                    if (poss[otherHash] == 2) twos.insert(otherHash);
                    lnk[otherHash] ^= edge;
                    cnt++;
                    used.insert(edge);
                }
                cnt++;
                used.insert(i);
                break;
            }
        }
    }
 
    vector<int> u, v;
    for (int i = 0; i < edges.size(); i++) {
        u.push_back(coords[edges[i].first].second);
        v.push_back(coords[edges[i].second].second);
        unite(edges[i].first, edges[i].second);
    }
 
    if (sz[find(0)] < n) return 0;
 
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
parks.cpp:116:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     while (cnt < edges.size()) {
      |            ~~~~^~~~~~~~~~~~~~
parks.cpp:132:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         if (cnt < edges.size()) {
      |             ~~~~^~~~~~~~~~~~~~
parks.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 626 ms 110452 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 1116 KB Output is correct
26 Correct 3 ms 1884 KB Output is correct
27 Correct 6 ms 2392 KB Output is correct
28 Correct 176 ms 44108 KB Output is correct
29 Correct 336 ms 71028 KB Output is correct
30 Correct 468 ms 88436 KB Output is correct
31 Correct 611 ms 109972 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1368 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 198 ms 45944 KB Output is correct
46 Correct 352 ms 68284 KB Output is correct
47 Correct 326 ms 67420 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 626 ms 110452 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 1116 KB Output is correct
26 Correct 3 ms 1884 KB Output is correct
27 Correct 6 ms 2392 KB Output is correct
28 Correct 176 ms 44108 KB Output is correct
29 Correct 336 ms 71028 KB Output is correct
30 Correct 468 ms 88436 KB Output is correct
31 Correct 611 ms 109972 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1368 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 198 ms 45944 KB Output is correct
46 Correct 352 ms 68284 KB Output is correct
47 Correct 326 ms 67420 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Runtime error 0 ms 348 KB Execution killed with signal 11
52 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 440 ms 86404 KB Output is correct
21 Correct 568 ms 87220 KB Output is correct
22 Correct 479 ms 86904 KB Output is correct
23 Correct 387 ms 84456 KB Output is correct
24 Correct 50 ms 21700 KB Output is correct
25 Correct 420 ms 105340 KB Output is correct
26 Correct 423 ms 104520 KB Output is correct
27 Correct 492 ms 110080 KB Output is correct
28 Correct 486 ms 110284 KB Output is correct
29 Correct 452 ms 111028 KB Output is correct
30 Correct 436 ms 110048 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Runtime error 19 ms 11736 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct
17 Correct 599 ms 110720 KB Output is correct
18 Runtime error 466 ms 207300 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 210 ms 55424 KB Output is correct
10 Correct 12 ms 5332 KB Output is correct
11 Correct 85 ms 29352 KB Output is correct
12 Correct 19 ms 8172 KB Output is correct
13 Correct 64 ms 23964 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 214 ms 55640 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 626 ms 110452 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 1116 KB Output is correct
26 Correct 3 ms 1884 KB Output is correct
27 Correct 6 ms 2392 KB Output is correct
28 Correct 176 ms 44108 KB Output is correct
29 Correct 336 ms 71028 KB Output is correct
30 Correct 468 ms 88436 KB Output is correct
31 Correct 611 ms 109972 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1368 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 198 ms 45944 KB Output is correct
46 Correct 352 ms 68284 KB Output is correct
47 Correct 326 ms 67420 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Runtime error 0 ms 348 KB Execution killed with signal 11
52 Halted 0 ms 0 KB -