Submission #1052824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052824		becaido	Simurgh (IOI17_simurgh)	C++17	100 / 100	141 ms	7320 KiB

simurgh

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#include "grader.cpp"
#else
#include "simurgh.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 505;
const int MSIZ = SIZE * SIZE / 2;

int n, m;
pair<int, int> ed[MSIZ];
vector<pair<int, int>> adj[SIZE];
int h[SIZE], pa[SIZE], pid[SIZE];

vector<int> tree;
bool is_tree[MSIZ];
int tree_cnt, ty[MSIZ];

struct DSU {
    int n;
    vector<int> to, h;
    void init(int n_) {
        n = n_;
        to.resize(n + 1);
        h.resize(n + 1);
        iota(to.begin() + 1, to.end(), 1);
        fill(h.begin() + 1, h.end(), 0);
    }
    int dsu(int x) {
        return x == to[x] ? x : (to[x] = dsu(to[x]));
    }
    bool merge(int a, int b, bool f = 0) {
        a = dsu(a), b = dsu(b);
        if (a == b) return 0;
        if (h[a] < h[b]) swap(a, b);
        to[b] = a;
        h[a] += (h[a] == h[b]);
        if (f) ty[a] = ty[b] = (ty[a] < 2 ? ty[a] : ty[b]);
        return 1;
    }
} mdsu;

void dfs(int pos) {
    for (auto [np, id] : adj[pos]) if (h[np] == 0) {
        h[np] = h[pos] + 1;
        pa[np] = pos;
        pid[np] = id;
        tree.pb(id);
        is_tree[id] = 1;
        dfs(np);
    }
}
int que(vector<int> e) {
    for (int &id : e) id--;
    return count_common_roads(e);
}
int ask(int x, int y) {
    vector<int> e;
    e.pb(y);
    for (int id : tree) if (x != id) e.pb(id);
    return que(e);
}
int ask_forest(vector<int> e) {
    DSU g;
    g.init(n);
    for (int id : e) {
        auto [x, y] = ed[id];
        g.merge(x, y);
    }
    int cnt = 0;
    for (int id : tree) {
        auto [x, y] = ed[id];
        if (g.merge(x, y)) {
            e.pb(id);
            cnt -= ty[id];
        }
    }
    cnt += que(e);
    return cnt;
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
    n = n_, m = u.size();
    FOR (i, 1, n) {
        adj[i].clear();
        h[i] = pa[i] = pid[i] = 0;
    }
    u.insert(u.begin(), 0);
    v.insert(v.begin(), 0);
    FOR (i, 1, m) {
        is_tree[i] = 0;
        u[i]++, v[i]++;
        ed[i] = {u[i], v[i]};
        adj[u[i]].pb(v[i], i);
        adj[v[i]].pb(u[i], i);
    }
    tree.clear();
    h[1] = 1, dfs(1);
    tree_cnt = que(tree);
    fill(ty + 1, ty + m + 1, 2);
    mdsu.init(m);
    FOR (i, 1, m) if (is_tree[i] == 0) {
        int a = u[i], b = v[i];
        if (h[a] > h[b]) swap(a, b);
        vector<int> e;
        int o = 0;
        while (h[a] < h[b]) {
            if (ty[mdsu.dsu(pid[b])] == 2) e.pb(pid[b]);
            else o = pid[b];
            b = pa[b];
        }
        if (e.size() == 0) continue;
        for (int j : e) {
            int cnt = ask(j, i);
            if (tree_cnt == cnt) mdsu.merge(i, j, 1);
            else if (tree_cnt < cnt) ty[mdsu.dsu(i)] = 1, ty[mdsu.dsu(j)] = 0;
            else ty[mdsu.dsu(i)] = 0, ty[mdsu.dsu(j)] = 1;
        }
        if (ty[mdsu.dsu(i)] == 2) {
            if (o == 0) ty[mdsu.dsu(i)] = 0;
            else {
                int cnt = ask(o, i);
                if (tree_cnt == cnt) mdsu.merge(o, i, 1);
                else ty[mdsu.dsu(i)] = (tree_cnt < cnt);
            }
        }
    }
    for (int id : tree) if (ty[mdsu.dsu(id)] == 2) ty[mdsu.dsu(id)] = 1;
    FOR (i, 1, m) ty[i] = ty[mdsu.dsu(i)];

    DSU g;
    g.init(n);
    for (int id : tree) {
        auto [x, y] = ed[id];
        if (ty[id] == 1) g.merge(x, y);
    }
    FOR (i, 1, n) {
        vector<int> e;
        for (auto [j, id] : adj[i]) {
            auto [x, y] = ed[id];
            if (ty[id] == 2 && g.dsu(x) != g.dsu(y)) e.pb(id);
        }
        if (e.size() == 0) continue;
        auto rec = [&](auto rec, int l, int r, int tot)->void {
            if (tot == 0) {
                FOR (j, l, r) ty[e[j]] = 0;
                return;
            }
            if (tot == r - l + 1) {
                FOR (j, l, r) {
                    auto [x, y] = ed[e[j]];
                    ty[e[j]] = 1;
                    g.merge(x, y);
                }
                return;
            }
            int mid = (l + r) / 2, lc;
            vector<int> le;
            FOR (j, l, mid) le.pb(e[j]);
            lc = ask_forest(le);
            rec(rec, l, mid, lc);
            rec(rec, mid + 1, r, tot - lc);
        };
        rec(rec, 0, e.size() - 1, ask_forest(e));
    }
    vector<int> ans;
    FOR (i, 1, m) if (ty[i] == 1) ans.pb(i - 1);
    return ans;
}

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