oj.uz

Submission #435744

# Submission time Handle Problem Language Result Execution time Memory
435744 2021-06-23T16:28:37 Z talant117408 Fountain Parks (IOI21_parks) C++17
55 / 100
 1254 ms 92048 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

const int MAXN = 6e5+7;
vector <int> graph[MAXN];
int N, RN, BN, degree[MAXN], parent[MAXN];
int used[MAXN];
int link[MAXN], saizu[MAXN];
int x[MAXN], y[MAXN];
vector <int> WrongRoads;
int numOfWrongRoads;
pii roads[MAXN];
vector <pii> benches;

int find(int n) {
    if (n == link[n]) return n;
    return link[n] = find(link[n]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (saizu[a] < saizu[b]) swap(a, b);
    saizu[a] += saizu[b];
    link[b] = a;
}

bool same(int a, int b) {
    return find(a) == find(b);
}

void dfs(int v) {
    used[v] = 1;
    for (auto to : graph[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

void dfs2(int v, int p) {
    used[v] = 1;
    if (v < RN && sz(graph[v]) == 1) {
        WrongRoads.pb(v);
        numOfWrongRoads++;
    }
    for (auto to : graph[v]) {
        if (!used[to]) {
            dfs2(to, v);
        }
    }
    used[v] = 2;
}

void dfs3(int v, int p) {
    parent[v] = p;
    used[v] = 1;
    for (auto to : graph[v]) {
        if (used[to]) continue;
        degree[v]++;
        dfs3(to, v);
    }
}

int construct_roads(vector<int> X, vector<int> Y) {
    N = sz(X);
    
    if (N == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    
    for (int i = 0; i < N; i++) {
        link[i] = i;
        saizu[i] = 1;
        x[i] = X[i];
        y[i] = Y[i];
    }
    X.clear(); Y.clear();
    
    //***************** get roads and benches *****************
    vector <pair <pii, int>> tmp;
    vector <pii> edges;
    set <pii> tmpBenches;
    for (int i = 0; i < N; i++) {
        tmp.pb(mp(mp(x[i], y[i]), i));
    }
    sort(all(tmp));
    for (int i = 0; i < N; i++) {
        auto it = lb(all(tmp), mp(mp(x[i]-2, y[i]), 0));
        if (it != tmp.end() && (*it).first == mp(x[i]-2, y[i])) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i]+2, y[i]), 0));
        if (it != tmp.end() && (*it).first == mp(x[i]+2, y[i])) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i], y[i]-2), 0));
        if (it != tmp.end() && (*it).first == mp(x[i], y[i]-2)) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i], y[i]+2), 0));
        if (it != tmp.end() && (*it).first == mp(x[i], y[i]+2)) {
            edges.pb(mp(i, (*it).second));
        }
    }
    for (auto &to : edges) {
        if (mp(x[to.first], y[to.first]) > mp(x[to.second], y[to.second])) {
            swap(to.first, to.second);
        }
        if (!same(to.first, to.second)) {
            unite(to.first, to.second);
            graph[to.first].pb(to.second);
            graph[to.second].pb(to.first);
            roads[RN++] = mp(to.first, to.second);
            if (x[to.first] == x[to.second]) {
                tmpBenches.insert(mp(x[to.first]-1, y[to.first]+1));
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
            }
            else {
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]-1));
            }
        }
    }
    for (auto to : tmpBenches) {
        benches.pb(to);
    }
    BN = sz(benches);
    //***************** get roads and benches *****************
    
    //***************** check if connected ***************** 
    dfs(0);
    bool flag = 1;
    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            flag = 0;
            break;
        }
    }
    if (!flag) {
        return 0;
    }
    for (int i = 0; i < RN+BN; i++) {
        link[i] = i;
        saizu[i] = 1;
        used[i] = 0;
        graph[i].clear();
    }
    edges.clear();
    //***************** check if connected ***************** 
    
    //***************** create a new graph *****************
    for (int i = 0; i < RN; i++) {
        auto a = roads[i].first, b = roads[i].second;
        if (x[a] == x[b]) {
            auto it = lb(all(benches), mp(x[a]-1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
            it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
        }
        else {
            auto it = lb(all(benches), mp(x[a]+1, y[a]-1))-benches.begin();
            edges.pb(mp(i, it+RN));
            it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
        }
    }
    for (auto to : edges) {
        if (!same(to.first, to.second)) {
            unite(to.first, to.second);
            graph[to.first].pb(to.second);
            graph[to.second].pb(to.first);
        }
    }
    for (int i = 0; i < RN; i++) {
        if (!used[i]) {
            numOfWrongRoads = 0;
            dfs2(i, i);
            if (numOfWrongRoads) {
                WrongRoads.pop_back();
            }
        }
    }
    for (int i = 0; i < RN+BN; i++) {
        used[i] = 0;
    }
    for (auto to : WrongRoads) {
        used[to] = 1;
    }
    for (int i = 0; i < RN; i++) {
        if (!used[i] && sz(graph[i]) == 1) {
            dfs3(i, i);
        }
    }
    for (int i = 0; i < RN; i++) {
        if (!used[i]) {
            dfs3(i, i);
        }
    }
    for (int i = 0; i < RN+BN; i++) {
        used[i] = 0;
    }
    //***************** create a new graph *****************
    
    //***************** get the answer *****************
    vector <int> _u, _v, _x, _y;
    queue <int> K;
    for (int i = RN; i < RN+BN; i++) {
        if (!degree[i]) {
            K.push(i);
        }
    }
    while (!K.empty()) {
        auto v = K.front(); K.pop();
        if (!used[v] && !used[parent[v]]) {
            used[v] = 1;
            used[parent[v]] = 1;
            _u.pb(roads[parent[v]].first);
            _v.pb(roads[parent[v]].second);
            _x.pb(benches[v-RN].first);
            _y.pb(benches[v-RN].second);
            v = parent[parent[v]];
            if (v >= RN) {
                degree[v]--;
                if (!used[v] && !degree[v]) {
                    K.push(v);
                }
            }
        }
    }
    build(_u, _v, _x, _y);
    //***************** get the answer *****************
    
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 8 ms 14412 KB Output is correct
20 Correct 10 ms 14412 KB Output is correct
21 Correct 11 ms 14412 KB Output is correct
22 Correct 10 ms 14412 KB Output is correct
23 Correct 1037 ms 74016 KB Output is correct
24 Correct 9 ms 14412 KB Output is correct
25 Correct 12 ms 14796 KB Output is correct
26 Correct 13 ms 14900 KB Output is correct
27 Correct 15 ms 15056 KB Output is correct
28 Correct 325 ms 38552 KB Output is correct
29 Correct 551 ms 49624 KB Output is correct
30 Correct 757 ms 62912 KB Output is correct
31 Correct 1059 ms 73908 KB Output is correct
32 Correct 11 ms 14404 KB Output is correct
33 Correct 9 ms 14412 KB Output is correct
34 Correct 9 ms 14412 KB Output is correct
35 Correct 9 ms 14412 KB Output is correct
36 Correct 12 ms 14376 KB Output is correct
37 Correct 11 ms 14412 KB Output is correct
38 Correct 10 ms 14332 KB Output is correct
39 Correct 9 ms 14412 KB Output is correct
40 Correct 10 ms 14412 KB Output is correct
41 Correct 9 ms 14412 KB Output is correct
42 Correct 9 ms 14412 KB Output is correct
43 Correct 13 ms 14796 KB Output is correct
44 Correct 14 ms 15024 KB Output is correct
45 Correct 471 ms 46040 KB Output is correct
46 Correct 771 ms 61368 KB Output is correct
47 Correct 764 ms 61204 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 8 ms 14412 KB Output is correct
20 Correct 10 ms 14412 KB Output is correct
21 Correct 11 ms 14412 KB Output is correct
22 Correct 10 ms 14412 KB Output is correct
23 Correct 1037 ms 74016 KB Output is correct
24 Correct 9 ms 14412 KB Output is correct
25 Correct 12 ms 14796 KB Output is correct
26 Correct 13 ms 14900 KB Output is correct
27 Correct 15 ms 15056 KB Output is correct
28 Correct 325 ms 38552 KB Output is correct
29 Correct 551 ms 49624 KB Output is correct
30 Correct 757 ms 62912 KB Output is correct
31 Correct 1059 ms 73908 KB Output is correct
32 Correct 11 ms 14404 KB Output is correct
33 Correct 9 ms 14412 KB Output is correct
34 Correct 9 ms 14412 KB Output is correct
35 Correct 9 ms 14412 KB Output is correct
36 Correct 12 ms 14376 KB Output is correct
37 Correct 11 ms 14412 KB Output is correct
38 Correct 10 ms 14332 KB Output is correct
39 Correct 9 ms 14412 KB Output is correct
40 Correct 10 ms 14412 KB Output is correct
41 Correct 9 ms 14412 KB Output is correct
42 Correct 9 ms 14412 KB Output is correct
43 Correct 13 ms 14796 KB Output is correct
44 Correct 14 ms 15024 KB Output is correct
45 Correct 471 ms 46040 KB Output is correct
46 Correct 771 ms 61368 KB Output is correct
47 Correct 764 ms 61204 KB Output is correct
48 Correct 9 ms 14412 KB Output is correct
49 Correct 10 ms 14408 KB Output is correct
50 Correct 9 ms 14368 KB Output is correct
51 Correct 12 ms 14412 KB Output is correct
52 Correct 9 ms 14412 KB Output is correct
53 Correct 10 ms 14412 KB Output is correct
54 Correct 9 ms 14412 KB Output is correct
55 Incorrect 1004 ms 71900 KB Given structure is not connected: There is no path between vertices 0 and 1
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct
17 Correct 9 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 10 ms 14412 KB Output is correct
20 Correct 1073 ms 92048 KB Output is correct
21 Correct 1078 ms 74644 KB Output is correct
22 Correct 1060 ms 75724 KB Output is correct
23 Correct 857 ms 80140 KB Output is correct
24 Correct 198 ms 23768 KB Output is correct
25 Correct 680 ms 58816 KB Output is correct
26 Correct 609 ms 58928 KB Output is correct
27 Correct 1124 ms 90344 KB Output is correct
28 Correct 1094 ms 90312 KB Output is correct
29 Correct 1152 ms 88816 KB Output is correct
30 Correct 1079 ms 88692 KB Output is correct
31 Correct 10 ms 14412 KB Output is correct
32 Correct 51 ms 18692 KB Output is correct
33 Correct 101 ms 19144 KB Output is correct
34 Correct 1016 ms 88080 KB Output is correct
35 Correct 25 ms 16192 KB Output is correct
36 Correct 105 ms 23228 KB Output is correct
37 Correct 272 ms 32136 KB Output is correct
38 Correct 488 ms 37788 KB Output is correct
39 Correct 552 ms 45880 KB Output is correct
40 Correct 737 ms 55640 KB Output is correct
41 Correct 940 ms 63812 KB Output is correct
42 Correct 1174 ms 71864 KB Output is correct
43 Correct 9 ms 14412 KB Output is correct
44 Correct 9 ms 14412 KB Output is correct
45 Correct 9 ms 14412 KB Output is correct
46 Correct 9 ms 14412 KB Output is correct
47 Correct 10 ms 14412 KB Output is correct
48 Correct 10 ms 14380 KB Output is correct
49 Correct 11 ms 14432 KB Output is correct
50 Correct 9 ms 14448 KB Output is correct
51 Correct 10 ms 14412 KB Output is correct
52 Correct 10 ms 14412 KB Output is correct
53 Correct 9 ms 14412 KB Output is correct
54 Correct 13 ms 14752 KB Output is correct
55 Correct 13 ms 14924 KB Output is correct
56 Correct 472 ms 46112 KB Output is correct
57 Correct 796 ms 61416 KB Output is correct
58 Correct 730 ms 61280 KB Output is correct
59 Correct 9 ms 14412 KB Output is correct
60 Correct 9 ms 14412 KB Output is correct
61 Correct 9 ms 14412 KB Output is correct
62 Correct 1115 ms 91308 KB Output is correct
63 Correct 1074 ms 91388 KB Output is correct
64 Correct 1097 ms 91428 KB Output is correct
65 Correct 15 ms 15180 KB Output is correct
66 Correct 21 ms 15936 KB Output is correct
67 Correct 489 ms 45140 KB Output is correct
68 Correct 764 ms 61760 KB Output is correct
69 Correct 1254 ms 76004 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct
17 Correct 1143 ms 91832 KB Output is correct
18 Correct 1076 ms 90572 KB Output is correct
19 Correct 1148 ms 88188 KB Output is correct
20 Correct 1040 ms 72756 KB Output is correct
21 Correct 976 ms 74628 KB Output is correct
22 Correct 9 ms 14360 KB Output is correct
23 Correct 107 ms 23712 KB Output is correct
24 Correct 49 ms 18068 KB Output is correct
25 Correct 171 ms 27484 KB Output is correct
26 Correct 343 ms 37168 KB Output is correct
27 Correct 460 ms 43964 KB Output is correct
28 Correct 687 ms 51060 KB Output is correct
29 Correct 817 ms 59652 KB Output is correct
30 Correct 949 ms 66768 KB Output is correct
31 Correct 1094 ms 73684 KB Output is correct
32 Correct 1064 ms 79628 KB Output is correct
33 Correct 1029 ms 91828 KB Output is correct
34 Correct 16 ms 15308 KB Output is correct
35 Correct 25 ms 16084 KB Output is correct
36 Correct 455 ms 45636 KB Output is correct
37 Correct 781 ms 62148 KB Output is correct
38 Correct 1152 ms 77188 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14536 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 429 ms 53176 KB Output is correct
10 Correct 27 ms 18348 KB Output is correct
11 Correct 121 ms 35296 KB Output is correct
12 Correct 36 ms 20236 KB Output is correct
13 Correct 65 ms 24380 KB Output is correct
14 Correct 11 ms 14644 KB Output is correct
15 Correct 11 ms 14796 KB Output is correct
16 Correct 469 ms 52420 KB Output is correct
17 Correct 8 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 8 ms 14412 KB Output is correct
20 Correct 10 ms 14412 KB Output is correct
21 Correct 11 ms 14412 KB Output is correct
22 Correct 10 ms 14412 KB Output is correct
23 Correct 1037 ms 74016 KB Output is correct
24 Correct 9 ms 14412 KB Output is correct
25 Correct 12 ms 14796 KB Output is correct
26 Correct 13 ms 14900 KB Output is correct
27 Correct 15 ms 15056 KB Output is correct
28 Correct 325 ms 38552 KB Output is correct
29 Correct 551 ms 49624 KB Output is correct
30 Correct 757 ms 62912 KB Output is correct
31 Correct 1059 ms 73908 KB Output is correct
32 Correct 11 ms 14404 KB Output is correct
33 Correct 9 ms 14412 KB Output is correct
34 Correct 9 ms 14412 KB Output is correct
35 Correct 9 ms 14412 KB Output is correct
36 Correct 12 ms 14376 KB Output is correct
37 Correct 11 ms 14412 KB Output is correct
38 Correct 10 ms 14332 KB Output is correct
39 Correct 9 ms 14412 KB Output is correct
40 Correct 10 ms 14412 KB Output is correct
41 Correct 9 ms 14412 KB Output is correct
42 Correct 9 ms 14412 KB Output is correct
43 Correct 13 ms 14796 KB Output is correct
44 Correct 14 ms 15024 KB Output is correct
45 Correct 471 ms 46040 KB Output is correct
46 Correct 771 ms 61368 KB Output is correct
47 Correct 764 ms 61204 KB Output is correct
48 Correct 9 ms 14412 KB Output is correct
49 Correct 10 ms 14408 KB Output is correct
50 Correct 9 ms 14368 KB Output is correct
51 Correct 12 ms 14412 KB Output is correct
52 Correct 9 ms 14412 KB Output is correct
53 Correct 10 ms 14412 KB Output is correct
54 Correct 9 ms 14412 KB Output is correct
55 Incorrect 1004 ms 71900 KB Given structure is not connected: There is no path between vertices 0 and 1
56 Halted 0 ms 0 KB -