oj.uz

Submission #483252

# Submission time Handle Problem Language Result Execution time Memory
483252 2021-10-28T11:13:41 Z lukaszgniecki Connecting Supertrees (IOI20_supertrees) C++17
100 / 100
 322 ms 23172 KB 
#include "supertrees.h"
#include <bits/stdc++.h>

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)

using namespace std;

//TODO: SOLUTION
int n;

bool contains3(vvi & paths) {
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (paths[i][j] == 3)
                return true;
        }
    }
    return false;
}

bool trees_are_fine(vvi & paths, vi & treeof) {
    rep(x, 0, n) {
        rep(y, 0, n) {
            if (treeof[x] == treeof[y] && paths[x][y] != 1)
                return false;
            if (treeof[x] != treeof[y] && paths[x][y] == 1)
                return false;
        }
    }

    return true;
}

bool trees_connected(vvi & paths, vi & t1, vi & t2) {
    for (int x : t1) {
        for (int y : t2) {
            if (paths[x][y] != 2)
                return false;
        }
    }
    return true;
}

bool cycle_contains(vvi & paths, vi & cycle, vvi & trees, vi & tr) {
    for (int tidx : cycle) {
        auto & cyc_tree = trees[tidx];
        if (!trees_connected(paths, cyc_tree, tr))
            return false;
    }
    return true;
}

bool cycles_are_fine(vvi & paths, vi & cycleof, vvi & trees) {
    rep(i, 0, trees.size()) {
        rep(j, 0, trees.size()) {
            if (i == j)
                continue;
            if (cycleof[i] == cycleof[j] && !trees_connected(paths, trees[i], trees[j]))
                return false;
            if (cycleof[i] != cycleof[j] && trees_connected(paths, trees[i], trees[j]))
                return false;
        }
    }
    return true;
}

bool connect_trees(vvi & gr, vvi & trees) {
    for (auto & tr : trees) {
        rep(i, 1, tr.size()) {
            gr[tr[i]][tr[i - 1]] = gr[tr[i - 1]][tr[i]] = 1;
        }
    }
    return true;
}

bool connect_cycles(vvi & gr, vvi & cycles, vvi & trees) {
    for (auto & cyc : cycles) {
        if (cyc.size() == 2)
            return false;
        if (cyc.size() == 1)
            continue;

        rep(i, 0, cyc.size()) {
            int x = cyc[i];
            int y = cyc[(i + 1) % cyc.size()];
            gr[trees[x][0]][trees[y][0]] = gr[trees[y][0]][trees[x][0]] = 1;
        }
    }

    return true;
}

/*void build(vvi gr) {
    rep(i, 0, n) {
        rep(j, 0, n) {
            cerr << gr[i][j] << ' ';
        }
        cerr << '\n';
    }
}*/

int construct(vvi paths) {
    n = paths.size();

    // contains 3 => not possible
    if (contains3(paths))
        return 0;

    // construct maximal trees
    vvi trees;
    vi treeof(n, 0);

    rep(x, 0, n) {
        bool found_tree = false;

        rep(i, 0, trees.size()) {
            auto & tr = trees[i];
            bool this_tree = true;

            for (int y : tr) {
                if (paths[x][y] != 1) {
                    this_tree = false;
                    break;
                }
            }

            if (this_tree) {
                tr.push_back(x);
                treeof[x] = i;
                found_tree = true;
                break;
            }
        }

        if (!found_tree) {
            trees.push_back({x});
            treeof[x] = trees.size() - 1;
        }
    }

    // check if partition into trees is correct
    if (!trees_are_fine(paths, treeof))
        return 0;

    // form cycles on trees
    vvi cycles; // trees are now vertices
    vi cycleof(trees.size());

    rep(t, 0, trees.size()) {
        vi & tr = trees[t];

        bool cycle_found = false;
        rep(i, 0, cycles.size()) {
            auto & cyc = cycles[i];
            if (cycle_contains(paths, cyc, trees, tr)) {
                cycleof[t] = i;
                cyc.push_back(t);
                cycle_found = true;
            }
        }

        if (!cycle_found) {
            cycles.push_back({t});
            cycleof[t] = cycles.size() - 1;
        }
    }

    // validate cycles
    if (!cycles_are_fine(paths, cycleof, trees))
        return 0;

    // construct graph
    vvi gr(n, vi(n, 0));
    if (!connect_trees(gr, trees))
        return 0;
    if (!connect_cycles(gr, cycles, trees))
        return 0;

    // build the graph
    rep(i, 0, n) gr[i][i] = 0;
    build(gr);
    return 1;
}

/*
int main() {
    vvi p1 = {{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}};
    vvi p2 = {{1, 0}, {0, 1}};
    vvi p3 = {
            {1, 2, 2, 2, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
            {2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}
    };
    cout << construct(p1) << endl;
    cout << construct(p2) << endl;
    cout << construct(p3) << endl;
}*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 1228 KB Output is correct
7 Correct 171 ms 22880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 1228 KB Output is correct
7 Correct 171 ms 22880 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 12 ms 1244 KB Output is correct
13 Correct 221 ms 23148 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 84 ms 9208 KB Output is correct
18 Correct 1 ms 224 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 6260 KB Output is correct
21 Correct 198 ms 22980 KB Output is correct
22 Correct 219 ms 23116 KB Output is correct
23 Correct 194 ms 22988 KB Output is correct
24 Correct 224 ms 23080 KB Output is correct
25 Correct 120 ms 9184 KB Output is correct
26 Correct 65 ms 9144 KB Output is correct
27 Correct 179 ms 23020 KB Output is correct
28 Correct 174 ms 23172 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 8 ms 1268 KB Output is correct
9 Correct 184 ms 23172 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 8 ms 1196 KB Output is correct
13 Correct 192 ms 23060 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 80 ms 9208 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 58 ms 6248 KB Output is correct
22 Correct 229 ms 23016 KB Output is correct
23 Correct 228 ms 23108 KB Output is correct
24 Correct 253 ms 23100 KB Output is correct
25 Correct 216 ms 13236 KB Output is correct
26 Correct 109 ms 9208 KB Output is correct
27 Correct 188 ms 23104 KB Output is correct
28 Correct 289 ms 23040 KB Output is correct
29 Correct 206 ms 13252 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 292 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 44 ms 6244 KB Output is correct
5 Correct 200 ms 23128 KB Output is correct
6 Correct 170 ms 23108 KB Output is correct
7 Correct 206 ms 23116 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 56 ms 6216 KB Output is correct
10 Correct 242 ms 23076 KB Output is correct
11 Correct 186 ms 23104 KB Output is correct
12 Correct 203 ms 23092 KB Output is correct
13 Correct 3 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 44 ms 6204 KB Output is correct
17 Correct 184 ms 23112 KB Output is correct
18 Correct 322 ms 23116 KB Output is correct
19 Correct 194 ms 23020 KB Output is correct
20 Correct 183 ms 23080 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 1228 KB Output is correct
7 Correct 171 ms 22880 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 12 ms 1244 KB Output is correct
13 Correct 221 ms 23148 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 84 ms 9208 KB Output is correct
18 Correct 1 ms 224 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 6260 KB Output is correct
21 Correct 198 ms 22980 KB Output is correct
22 Correct 219 ms 23116 KB Output is correct
23 Correct 194 ms 22988 KB Output is correct
24 Correct 224 ms 23080 KB Output is correct
25 Correct 120 ms 9184 KB Output is correct
26 Correct 65 ms 9144 KB Output is correct
27 Correct 179 ms 23020 KB Output is correct
28 Correct 174 ms 23172 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 292 KB Output is correct
33 Correct 1 ms 292 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 8 ms 1268 KB Output is correct
37 Correct 184 ms 23172 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 288 KB Output is correct
40 Correct 8 ms 1196 KB Output is correct
41 Correct 192 ms 23060 KB Output is correct
42 Correct 1 ms 204 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 4 ms 588 KB Output is correct
45 Correct 80 ms 9208 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 58 ms 6248 KB Output is correct
50 Correct 229 ms 23016 KB Output is correct
51 Correct 228 ms 23108 KB Output is correct
52 Correct 253 ms 23100 KB Output is correct
53 Correct 216 ms 13236 KB Output is correct
54 Correct 109 ms 9208 KB Output is correct
55 Correct 188 ms 23104 KB Output is correct
56 Correct 289 ms 23040 KB Output is correct
57 Correct 206 ms 13252 KB Output is correct
58 Correct 1 ms 292 KB Output is correct
59 Correct 1 ms 204 KB Output is correct
60 Correct 4 ms 588 KB Output is correct
61 Correct 79 ms 9212 KB Output is correct
62 Correct 0 ms 204 KB Output is correct
63 Correct 1 ms 204 KB Output is correct
64 Correct 1 ms 204 KB Output is correct
65 Correct 60 ms 6256 KB Output is correct
66 Correct 72 ms 9156 KB Output is correct
67 Correct 67 ms 9204 KB Output is correct
68 Correct 72 ms 9248 KB Output is correct
69 Correct 90 ms 13140 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 1228 KB Output is correct
7 Correct 171 ms 22880 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 12 ms 1244 KB Output is correct
13 Correct 221 ms 23148 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 84 ms 9208 KB Output is correct
18 Correct 1 ms 224 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 6260 KB Output is correct
21 Correct 198 ms 22980 KB Output is correct
22 Correct 219 ms 23116 KB Output is correct
23 Correct 194 ms 22988 KB Output is correct
24 Correct 224 ms 23080 KB Output is correct
25 Correct 120 ms 9184 KB Output is correct
26 Correct 65 ms 9144 KB Output is correct
27 Correct 179 ms 23020 KB Output is correct
28 Correct 174 ms 23172 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 292 KB Output is correct
33 Correct 1 ms 292 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 8 ms 1268 KB Output is correct
37 Correct 184 ms 23172 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 288 KB Output is correct
40 Correct 8 ms 1196 KB Output is correct
41 Correct 192 ms 23060 KB Output is correct
42 Correct 1 ms 204 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 4 ms 588 KB Output is correct
45 Correct 80 ms 9208 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 58 ms 6248 KB Output is correct
50 Correct 229 ms 23016 KB Output is correct
51 Correct 228 ms 23108 KB Output is correct
52 Correct 253 ms 23100 KB Output is correct
53 Correct 216 ms 13236 KB Output is correct
54 Correct 109 ms 9208 KB Output is correct
55 Correct 188 ms 23104 KB Output is correct
56 Correct 289 ms 23040 KB Output is correct
57 Correct 206 ms 13252 KB Output is correct
58 Correct 3 ms 292 KB Output is correct
59 Correct 3 ms 204 KB Output is correct
60 Correct 0 ms 204 KB Output is correct
61 Correct 44 ms 6244 KB Output is correct
62 Correct 200 ms 23128 KB Output is correct
63 Correct 170 ms 23108 KB Output is correct
64 Correct 206 ms 23116 KB Output is correct
65 Correct 1 ms 204 KB Output is correct
66 Correct 56 ms 6216 KB Output is correct
67 Correct 242 ms 23076 KB Output is correct
68 Correct 186 ms 23104 KB Output is correct
69 Correct 203 ms 23092 KB Output is correct
70 Correct 3 ms 204 KB Output is correct
71 Correct 1 ms 204 KB Output is correct
72 Correct 1 ms 204 KB Output is correct
73 Correct 44 ms 6204 KB Output is correct
74 Correct 184 ms 23112 KB Output is correct
75 Correct 322 ms 23116 KB Output is correct
76 Correct 194 ms 23020 KB Output is correct
77 Correct 183 ms 23080 KB Output is correct
78 Correct 1 ms 292 KB Output is correct
79 Correct 1 ms 204 KB Output is correct
80 Correct 4 ms 588 KB Output is correct
81 Correct 79 ms 9212 KB Output is correct
82 Correct 0 ms 204 KB Output is correct
83 Correct 1 ms 204 KB Output is correct
84 Correct 1 ms 204 KB Output is correct
85 Correct 60 ms 6256 KB Output is correct
86 Correct 72 ms 9156 KB Output is correct
87 Correct 67 ms 9204 KB Output is correct
88 Correct 72 ms 9248 KB Output is correct
89 Correct 90 ms 13140 KB Output is correct
90 Correct 1 ms 204 KB Output is correct
91 Correct 1 ms 204 KB Output is correct
92 Correct 4 ms 588 KB Output is correct
93 Correct 73 ms 9196 KB Output is correct
94 Correct 0 ms 204 KB Output is correct
95 Correct 0 ms 204 KB Output is correct
96 Correct 1 ms 204 KB Output is correct
97 Correct 19 ms 2664 KB Output is correct
98 Correct 89 ms 9152 KB Output is correct
99 Correct 87 ms 9184 KB Output is correct
100 Correct 65 ms 9180 KB Output is correct
101 Correct 85 ms 9160 KB Output is correct
102 Correct 64 ms 9132 KB Output is correct
103 Correct 65 ms 9140 KB Output is correct
104 Correct 65 ms 9156 KB Output is correct
105 Correct 88 ms 9164 KB Output is correct