Submission #431750

#	Time	Username	Problem	Language	Result	Execution time	Memory
431750		yuto1115	Simurgh (IOI17_simurgh)	C++17	70 / 100	223 ms	5864 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

vi find_roads(int n, vi u, vi v) {
    if (n == 2) {
        return {0};
    }
    int m = u.size();
    vvi G(n);
    vvi id(n, vi(n));
    rep(i, m) {
        G[u[i]].pb(v[i]);
        G[v[i]].pb(u[i]);
        id[u[i]][v[i]] = i;
        id[v[i]][u[i]] = i;
    }
    if(n <= 240) {
        vi par(n, inf);
        vi dep(n);
        vb on_tree(m);
        vi ori_edge;
        auto dfs = [&](auto &dfs, int now, int p, int d) -> void {
            par[now] = p;
            dep[now] = d;
            for (int nx : G[now]) {
                if (nx == p) continue;
                if (par[nx] != inf) continue;
                on_tree[id[now][nx]] = true;
                ori_edge.pb(id[now][nx]);
                dfs(dfs, nx, now, d + 1);
            }
        };
        dfs(dfs, 0, -1, 0);
        auto lca = [&](int i, int j) {
            if (dep[i] > dep[j]) swap(i, j);
            while (dep[i] < dep[j]) j = par[j];
            while (i != j) {
                i = par[i];
                j = par[j];
            }
            return i;
        };
        const int ori = count_common_roads(ori_edge);
        auto replace = [&](int add, int er) -> int {
            vi tmp = {add};
            for (int i : ori_edge) {
                if (i != er) tmp.pb(i);
            }
            return count_common_roads(tmp) - ori;
        };
        vi ans(m, -1);
        rep(i, m) {
            if (on_tree[i]) continue;
            assert(ans[i] == -1);
            int l = lca(u[i], v[i]);
            vi es;
            int now = u[i];
            while (now != l) {
                es.pb(id[now][par[now]]);
                now = par[now];
            }
            now = v[i];
            while (now != l) {
                es.pb(id[now][par[now]]);
                now = par[now];
            }
            int alr = -1;
            vi same = {(int) i}, dif;
            int self = -1;
            for (int j : es) {
                if (ans[j] == -1) {
                    int r = replace(i, j);
                    assert(-1 <= r and r <= 1);
                    if (r == 0) same.pb(j);
                    else {
                        dif.pb(j);
                        self = (r > 0 ? 1 : 0);
                    }
                } else {
                    alr = j;
                }
            }
            if (self != -1) {
                for (int j : same) ans[j] = self;
                for (int j : dif) ans[j] = self ^ 1;
                continue;
            }
            assert(dif.empty());
            if (alr == -1) {
                for (int j : same) ans[j] = 0;
            } else {
                int r = replace(i, alr);
                assert(0 <= ans[alr] + r and ans[alr] + r <= 1);
                for (int j : same) ans[j] = ans[alr] + r;
            }
        }
        vi res;
        rep(i, m) {
            if (ans[i] == 1 or ans[i] == -1) res.pb(i);
        }
        assert(res.size() == n - 1);
        return res;
    } else {
        vi ans(m, -1);
        vi ori_edge;
        rep2(i, 1, n) ori_edge.eb(id[0][i]);
        int ori = count_common_roads(ori_edge);
        rep2(i, 1, n) {
            int j = (i == n - 1 ? i - 1 : i + 1);
            vi ex_i, ex_j;
            rep2(k, 1, n) {
                if (k != i) ex_i.pb(id[0][k]);
                if (k != j) ex_j.pb(id[0][k]);
            }
            ex_i.pb(id[i][j]);
            ex_j.pb(id[i][j]);
            int a = count_common_roads(ex_i) - ori;
            int b = count_common_roads(ex_j) - ori;
            if (a != 0) {
                ans[id[0][i]] = (a > 0 ? 0 : 1);
                continue;
            }
            if (b != 0) {
                int t = (b > 0 ? 0 : 1);
                ans[id[0][i]] = t + b - a;
                continue;
            }
            ans[id[0][i]] = 0;
        }
        rep2(i, 1, n - 1) {
            auto calc = [&](int j) {
                assert(i + 1 < j and j <= n);
                vi tmp;
                int res = 0;
                rep(k, j) if (k != i) {
                        tmp.pb(id[i][k]);
                        if (k < i) res -= ans[id[i][k]];
                    }
                rep2(k, j, n) {
                    tmp.pb(id[0][k]);
                    res -= ans[id[0][k]];
                }
                res += count_common_roads(tmp);
                return res;
            };
            rep2(j, i + 1, n) ans[id[i][j]] = 0;
            int num = calc(n);
            rep2(j, 1, num + 1) {
                int ok = n, ng = i + 1;
                while (ok - ng > 1) {
                    int mid = (ok + ng) / 2;
                    (calc(mid) >= j ? ok : ng) = mid;
                }
                ans[id[i][ng]] = 1;
            }
        }
        vi res;
        rep(i, m) {
            assert(ans[i] != -1);
            if (ans[i]) res.pb(i);
        }
        assert(res.size() == n - 1);
        return res;
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:140:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |         assert(res.size() == n - 1);
      |                ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:201:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  201 |         assert(res.size() == n - 1);
      |                ~~~~~~~~~~~^~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30