oj.uz

Submission #1061565

# Submission time Handle Problem Language Result Execution time Memory
1061565 2024-08-16T10:56:03 Z TheQuantiX Fountain Parks (IOI21_parks) C++17
5 / 100
 799 ms 109236 KB 
#include<bits/stdc++.h>
#include "parks.h"
#pragma GCC optimize("O3,unroll-loops")

using namespace std;
using ll = int;

ll n, m, q, k, x, y, a, b, c;
unordered_map< long long, vector< pair< pair<ll, ll>, pair<ll, ll> > > > G;
vector< pair< pair<ll, ll>, pair<ll, ll> > > prs;

struct dsu {
    ll n;
    vector<ll> par;
    vector<ll> sz;
    
    dsu(ll N) : n(N) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    ll find_p(ll x) {
        if (par[x] == x) {
            return x;
        }
        ll p = find_p(par[x]);
        par[x] = p;
        return p;
    }

    void join(ll x, ll y) {
        x = find_p(x);
        y = find_p(y);
        if (x == y) {
            return;
        }
        if (sz[y] > sz[x]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};

long long hsh(pair<ll, ll> p) {
    return p.first * 10000000LL + p.second;
}

long long hsh(pair< pair<ll, ll>, pair<ll, ll> > p) {
    return (p.first.first * 10000000LL + p.first.second) + (10000000LL * 10000000LL * (p.first > p.second));
}

void dfs(pair< pair<ll, ll>, pair<ll, ll> > x, unordered_set<long long> &mp, vector< pair< pair<ll, ll>, pair<ll, ll> > > &mp1) {
    // cout << x.first.first << ' ';
    // cout << x.first.second << '\t';
    // cout << x.second.first << ' ';
    // cout << x.second.second << '\n';
    mp.insert(hsh(x));
    mp1.push_back(x);
    for (auto i : G[hsh(x)]) {
        if (!mp.count(hsh(i.first))) {
            dfs(i, mp, mp1);
        }
    }
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    array< vector<int>, 4 > ans;
    map< pair<ll, ll>, ll > pts;
    for (int i = 0; i < n; i++) {
        pts[{x[i], y[i]}] = i;
    }
    dsu d(n);
    map< pair<ll, ll>, vector< pair<ll, ll> > > vec;
    for (int i = 0; i < n; i++) {
        if (pts.count({x[i], y[i] - 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] - 2}])) {
            d.join(i, pts[{x[i], y[i] - 2}]);
            vec[{x[i] - 1, y[i] - 1}].push_back({x[i], y[i] - 1});
            vec[{x[i] + 1, y[i] - 1}].push_back({x[i], y[i] - 1});
        }
        if (pts.count({x[i], y[i] + 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] + 2}])) {
            d.join(i, pts[{x[i], y[i] + 2}]);
            vec[{x[i] - 1, y[i] + 1}].push_back({x[i], y[i] + 1});
            vec[{x[i] + 1, y[i] + 1}].push_back({x[i], y[i] + 1});
        }
    }
    for (int i = 0; i < n; i++) {
        if (pts.count({x[i] - 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] - 2, y[i]}])) {
            d.join(i, pts[{x[i] - 2, y[i]}]);
            vec[{x[i] - 1, y[i] + 1}].push_back({x[i] - 1, y[i]});
            vec[{x[i] - 1, y[i] - 1}].push_back({x[i] - 1, y[i]});
        }
        if (pts.count({x[i] + 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] + 2, y[i]}])) {
            d.join(i, pts[{x[i] + 2, y[i]}]);
            vec[{x[i] + 1, y[i] + 1}].push_back({x[i] + 1, y[i]});
            vec[{x[i] + 1, y[i] - 1}].push_back({x[i] + 1, y[i]});
        }
    }
    if (d.sz[d.find_p(0)] != n) {
        return 0;
    }
    for (auto &i : vec) {
        // cout << i.first.first << ' ' << i.first.second << '\n';
        for (auto j : i.second) {
            prs.push_back({j, i.first});
            // cout << '\t' << j.first << ' ' << j.second << '\n';
            for (auto k : i.second) {
                if (j != k) {
                    G[hsh({j, i.first})].push_back({k, {k.first + (k.first - i.first.first), k.second + (k.second - i.first.second)}});
                    // cout << "\t\t" << k.first + (k.first - i.first.first) << ' ' << k.second + (k.second - i.first.second) << '\n';
                }
            }
        }
    }
    unordered_set<long long> mp;
    for (auto i : prs) {
        // cout << i.first.first.first << ' ' << i.first.first.second << '\n';
        if (mp.count(hsh(i.first))) {
            continue;
        }
        vector< pair< pair<ll, ll>, pair<ll, ll> > > mp1;
        dfs(i, mp, mp1);
        for (auto j : mp1) {
            if (mp.count(hsh(j.first))) {
                continue;
            }
            if (j.first.first % 2 == 0) {
                ans[0].push_back(pts[{j.first.first, j.first.second - 1}]);
                ans[1].push_back(pts[{j.first.first, j.first.second + 1}]);
            }
            else {
                ans[0].push_back(pts[{j.first.first - 1, j.first.second}]);
                ans[1].push_back(pts[{j.first.first + 1, j.first.second}]);
            }
            ans[2].push_back(j.second.first);
            ans[3].push_back(j.second.second);
            mp.insert(hsh(j.first));
        }
    }
    build(ans[0], ans[1], ans[2], ans[3]);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct
17 Incorrect 0 ms 344 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct
17 Incorrect 0 ms 344 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 2
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct
17 Incorrect 799 ms 109236 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 324 ms 53808 KB Output is correct
10 Correct 16 ms 5588 KB Output is correct
11 Correct 106 ms 28992 KB Output is correct
12 Correct 26 ms 8148 KB Output is correct
13 Correct 57 ms 13900 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 311 ms 53892 KB Output is correct
17 Incorrect 0 ms 344 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -