Submission #431518

#	Time	Username	Problem	Language	Result	Execution time	Memory
431518		yuto1115	Simurgh (IOI17_simurgh)	C++17	51 / 100	225 ms	4068 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) {
    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;
    }
    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;
}

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:136:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |     assert(res.size() == n - 1);
      |            ~~~~~~~~~~~^~~~~~~~

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