oj.uz

Submission #642019

# Submission time Handle Problem Language Result Execution time Memory
642019 2022-09-18T09:53:37 Z piOOE Simurgh (IOI17_simurgh) C++17
0 / 100
 3000 ms 8936 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) {
    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);
        }
    }

    const int cnt_st = count_common_roads(st);
    vector<int> cnt(n - 1, cnt_st);
    for (int i = 0; i < n - 1; ++i) {
        int pos = st[i];
        vector<int> now = st;
        now.erase(now.begin() + i);

        dsu s(n);
        for (int j = 0; j < i; ++j) {
            s.unite(u[st[j]], v[st[j]]);
        }
        for (int j = i + 1; j < n - 1; ++j) {
            s.unite(u[st[j]], v[st[j]]);
        }

        for (int j = 0; j < m; ++j) {
            if (j != pos && !s.same(u[j], v[j])) {
                now.push_back(j);
                cnt[i] = min(cnt[i], count_common_roads(now));
                break;
            }
        }
    }

    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);
    }

    vector<pair<int, int>> par(n);
    vector<int> tin(n), tout(n);
    int T = 0;
    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);

    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;
    };

    vector<int> ans;
    for (int i = 0; i < m; ++i) {
        if (in_st[i]) {
            if (cnt[i] != cnt_st) {
                ans.push_back(i);
            }
        } else {
            int x = u[i], y = v[i];
            int j = -1;
            if (!isp(x, y)) {
                j = par[x].second;
            } else {
                j = par[y].second;
            }
            vector<int> now = st;
            auto it = find(now.begin(), now.end(), j);
            my_assert(it != now.end());
            now.erase(it);
            now.push_back(i);
            int val = count_common_roads(now);
            assert(val >= cnt[j]);
            if (val > cnt[j]) {
                ans.push_back(i);
            }
        }
    }
    return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:107:10: warning: variable 'path' set but not used [-Wunused-but-set-variable]
  107 |     auto path = [&](int x, int y) -> vector<int> {
      |          ^~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 8936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 8936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 8936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 8936 KB Time limit exceeded
2 Halted 0 ms 0 KB -