Submission #491758

#	Time	Username	Problem	Language	Result	Execution time	Memory
491758		maksim1744	Keys (IOI21_keys)	C++17	100 / 100	2407 ms	94444 KiB

keys

/*
    author:  Maksim1744
    created: 04.12.2021 11:30:50
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#endif

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
//     return b == 0 ? a : gcd(b, a % b);
// });


vector<int> scc(vector<vector<int>>& g, vector<vector<int>>& gi) {
    int n = g.size();
    vector<int> topsort; topsort.reserve(n);
    vector<bool> u(n, false);
    auto scc_dfs1 = y_combinator([&](auto scc_dfs1, int v) -> void {
        u[v] = true;
        for (auto k : g[v])
            if (!u[k])
                scc_dfs1(k);
        topsort.push_back(v);
    });
    for (int i = 0; i < n; ++i)
        if (!u[i])
            scc_dfs1(i);
    int color = 0;
    vector<int> comp(n, -1);
    reverse(topsort.begin(), topsort.end());
    auto scc_dfs2 = y_combinator([&](auto scc_dfs2, int v, int color) -> void {
        comp[v] = color;
        for (auto k : gi[v])
            if (comp[k] == -1)
                scc_dfs2(k, color);
    });
    for (auto v : topsort)
        if (comp[v] == -1)
            scc_dfs2(v, color++);
    return comp;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size();

    vector<vector<pair<int, pair<int, int>>>> g(n);
    for (int i = 0; i < u.size(); ++i) {
        g[u[i]].eb(v[i], mp(i * 2 + 0, c[i]));
        g[v[i]].eb(u[i], mp(i * 2 + 1, c[i]));
    }

    vector<vector<int>> go(n);
    vector<vector<int>> goi(n);
    vector<bool> ue(u.size() * 2, false);

    bool because_change = false;
    vector<int> cur(n, 0);
    int icur = 0;

    for (int iter = 0; iter < 1e2/2; ++iter) {
        bool change = false;

        auto col = scc(go, goi);
        vector<vector<int>> comps(maxe(col) + 1);
        for (int i = 0; i < n; ++i) {
            comps[col[i]].pb(i);
        }
        for (int i = 0; i < comps.size(); ++i) {
            ++icur;
            for (int v : comps[i]) {
                cur[r[v]] = icur;
            }
            for (int v : comps[i]) {
                for (auto [u, ic] : g[v]) {
                    auto [ind, c] = ic;
                    if (col[u] == col[v]) continue;
                    if (cur[c] != icur) continue;
                    if (ue[ind]) continue;
                    ue[ind] = true;
                    go[v].pb(u);
                    goi[u].pb(v);
                    change = true;
                }
            }
        }

        show(go, change);

        if (!change) {
            because_change = true;
            break;
        }
    }

    auto col = scc(go, goi);
    vector<bool> terminal(maxe(col) + 1, true);
    for (int i = 0; i < n; ++i) {
        for (auto j : go[i]) {
            if (col[i] == col[j]) continue;
            terminal[col[i]] = false;
        }
    }

    show(go);
    show(col);
    show(terminal);

    vector<int> sz(terminal.size(), 1e9);

    vector<pair<int, vector<int>>> tos(n, {-1, {}});
    vector<int> has(n, -1);
    int ihas = 0;
    vector<bool> uu(n, false);
    auto reachable = [&](int v) {
        ++ihas;
        queue<int> q;
        int ans = 0;
        q.push(v);
        uu.assign(n, false);
        while (!q.empty()) {
            auto v = q.front();
            q.pop();
            if (uu[v]) continue;
            uu[v] = true;
            ++ans;
            if (has[r[v]] != ihas) {
                has[r[v]] = ihas;
                if (tos[r[v]].first != ihas) tos[r[v]].second.clear();
                for (int k : tos[r[v]].second)
                    q.push(k);
            }
            for (auto [k, ic] : g[v]) {
                auto [ind, c] = ic;
                if (has[c] == ihas)
                    q.push(k);
                else {
                    if (tos[c].first != ihas) {
                        tos[c].first = ihas;
                        tos[c].second.clear();
                    }
                    tos[c].second.pb(k);
                }
            }
        }
        show(v, ans);
        return ans;
    };

    if (because_change) {
        for (int i = 0; i < n; ++i) {
            if (terminal[col[i]])
                sz[col[i]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            sz[col[i]]++;
        }
    } else {
        vector<int> check;
        for (int i = 0; i < n; ++i) {
            if (terminal[col[i]]) {
                terminal[col[i]] = false;
                check.pb(i);
            }
        }
        for (int v : check) {
            sz[col[v]] = reachable(v);
        }
    }
    show(sz);

    vector<int> ans(n, 0);
    int mnsz = mine(sz);
    for (int i = 0; i < n; ++i) {
        if (sz[col[i]] == mnsz) {
            ans[i] = 1;
        }
    }
    return ans;
}

#ifdef HOUSE

int main() {
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), c(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, c);

    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
#endif

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for (int i = 0; i < u.size(); ++i) {
      |                     ~~^~~~~~~~~~
keys.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int i = 0; i < comps.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33