oj.uz

Submission #642028

# Submission time Handle Problem Language Result Execution time Memory
642028 2022-09-18T10:07:46 Z piOOE Simurgh (IOI17_simurgh) C++17
30 / 100
 132 ms 2200 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

void my_assert(bool f) {
    if (!f) {
        cerr << "228\n";
        int x = 1337;
        while (!f) {
            x *= 2;
            cerr << "yay";
        }
    }
}

struct dsu {
    vector<int> p;

    dsu(int n = 0) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int x) {
        while (x != p[x]) x = p[x] = p[p[x]];
        return x;
    }

    bool same(int x, int y) {
        return get(x) == get(y);
    }

    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) {
            return false;
        }
        p[y] = x;
        return true;
    }
};


vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    vector<pair<int, int>> par(n);
    vector<int> tin(n), tout(n);
    int T = 0, ans_st = 0;

    auto calc = [&](vector<int> st) {
        T = 0;
        ans_st = count_common_roads(st);
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; ++i) {
            g[u[st[i]]].emplace_back(v[st[i]], i);
            g[v[st[i]]].emplace_back(u[st[i]], i);
        }
        function<void(int)> dfs = [&](int v) {
            tin[v] = T++;
            for (auto [to, i]: g[v]) {
                if (to != par[v].first) {
                    par[to] = {v, i};
                    dfs(to);
                }
            }
            tout[v] = T;
        };
        dfs(0);
    };

    int m = u.size();

    dsu d(n);
    vector<int> st;
    vector<bool> in_st(m);
    for (int i = 0; i < m; ++i) {
        in_st[i] = d.unite(u[i], v[i]);
        if (in_st[i]) {
            st.push_back(i);
        }
    }


    auto isp = [&](int x, int y) {
        return tin[x] <= tin[y] && tout[x] >= tout[y];
    };

    auto path = [&](int x, int y) -> vector<int> {
        int y_ = y, x_ = x;
        vector<int> ans;
        while (!isp(x, y_)) {
            ans.push_back(par[x].second);
            x = par[x].first;
        }
        while (!isp(y, x_)) {
            ans.push_back(par[y].second);
            y = par[y].first;
        }
        return ans;
    };

    calc(st);

    vector<bool> sure(m);

    for (int i = 0; i < m; ++i) {
        if (find(st.begin(), st.end(), i) == st.end()) {
            vector<int> now = path(u[i], v[i]);
            vector<int> vis;
            bool yay = false;
            for (int j: now) {
                if (!sure[st[j]]) {
                    auto q = st;
                    q.erase(q.begin() + j);
                    q.push_back(i);
                    int val = count_common_roads(q);
                    if (val > ans_st) {
                        st = q;
                        sure[i] = true;
                        calc(st);
                        yay = true;
                        break;
                    } else if (val < ans_st) {
                        sure[st[j]] = true;
                        break;
                    } else {
                        vis.push_back(st[j]);
                    }
                }
            }
            if (yay) {
                for (int j : vis) {
                    sure[j] = true;
                }
            }
        }
    }
    return st;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 5 ms 212 KB correct
15 Correct 3 ms 212 KB correct
16 Correct 3 ms 304 KB correct
17 Correct 4 ms 328 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 4 ms 212 KB correct
20 Correct 4 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 1 ms 300 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 296 KB correct
26 Correct 1 ms 300 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 296 KB correct
29 Correct 0 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 212 KB correct
33 Correct 1 ms 212 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 5 ms 212 KB correct
15 Correct 3 ms 212 KB correct
16 Correct 3 ms 304 KB correct
17 Correct 4 ms 328 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 4 ms 212 KB correct
20 Correct 4 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 1 ms 300 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 296 KB correct
26 Correct 1 ms 300 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 296 KB correct
29 Correct 0 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 212 KB correct
33 Correct 1 ms 212 KB correct
34 Incorrect 132 ms 964 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 304 KB correct
3 Incorrect 109 ms 2200 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 5 ms 212 KB correct
15 Correct 3 ms 212 KB correct
16 Correct 3 ms 304 KB correct
17 Correct 4 ms 328 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 4 ms 212 KB correct
20 Correct 4 ms 212 KB correct
21 Correct 3 ms 212 KB correct
22 Correct 1 ms 300 KB correct
23 Correct 1 ms 212 KB correct
24 Correct 1 ms 212 KB correct
25 Correct 1 ms 296 KB correct
26 Correct 1 ms 300 KB correct
27 Correct 1 ms 212 KB correct
28 Correct 1 ms 296 KB correct
29 Correct 0 ms 212 KB correct
30 Correct 1 ms 212 KB correct
31 Correct 1 ms 212 KB correct
32 Correct 1 ms 212 KB correct
33 Correct 1 ms 212 KB correct
34 Incorrect 132 ms 964 KB WA in grader: NO
35 Halted 0 ms 0 KB -