Submission #1011348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011348		c2zi6	Simurgh (IOI17_simurgh)	C++14	49 / 100	1764 ms	9404 KiB

simurgh

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "simurgh.h"

int count_common_roads2(VI a) {
    VI ret;
    rep(i, a.size()) if (a[i]) ret.pb(i);
    return count_common_roads(ret);
}

namespace TEST1 {
    int n;
    VVI gp;
    VI vis;
    void dfs(int u = 0) {
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) dfs(v);
    }
    bool istree(VPI edges) {
        gp = VVI(n);
        vis = VI(n);
        for (auto[u, v] : edges) {
            gp[u].pb(v);
            gp[v].pb(u);
        }
        dfs();
        rep(u, n) if (!vis[u]) return false;
        return true;
    }
    VI solve(int N, VI u, VI v) {
        n = N;
        int m = u.size();
        rep(s, 1<<m) {
            int cnt = 0;
            rep(i, m) if (s & (1<<i)) cnt++;
            if (cnt != n-1) continue;
            VPI edges;
            rep(i, m) if (s & (1<<i)) edges.pb({u[i], v[i]});
            if (!istree(edges)) continue;
            VI ret;
            rep(i, m) if (s & (1<<i)) ret.pb(i);
            if (count_common_roads(ret) == n-1) return ret;
        }
        return VI();
    }
};
namespace TEST2 {
    mt19937 rng;
    int n, m;
    VVPI gp;
    VI vis;
    VI par;
    VI parind;
    struct EDGE {
        int u, v, i;
        VI get() {
            VI ret;
            int cur = u;
            while (cur != v) {
                ret.pb(parind[cur]);
                cur = par[cur];
            }
            shuffle(all(ret), rng);
            return ret;
        }
    };
    vector<EDGE> back;
    VI op;
    void dfs(int u = 0, int p = -1, int pi = -1) {
        par[u] = p;
        parind[u] = pi;
        vis[u] = 1;
        for (auto[v, i] : gp[u]) if (i != pi) {
            if (vis[v] == 1) {
                back.pb({u, v, i});
                /*cout << "BACK: " << u << " " << v << " " << i << endl;*/
            } else if (vis[v] == 0) {
                /*cout << "SPAN: " << u << " " << v << " " << i << endl;*/
                op[i] = true;
                dfs(v, u, i);
            }
        }
        vis[u] = 2;
    }
    VVI gpa;
    VI comp;
    void dfs2(int u) {
        comp.pb(u);
        vis[u] = true;
        for (int v : gpa[u]) if (!vis[v]) {
            dfs2(v);
        }
    }
    VI solve(int N, VI U, VI V) {
        rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
        n = N;
        m = U.size();
        gp = VVPI(n);
        rep(i, m) {
            gp[U[i]].pb({V[i], i});
            gp[V[i]].pb({U[i], i});
        }
        vis = par = parind = VI(n);
        op = VI(m);
        dfs(rng()%n);
        /*dfs(0);*/
        VI tp(m);
        /*
         * 0 - unknown
         * 1 - regular
         * 2 - gold
         */
        int cnt = count_common_roads2(op);
        gpa = VVI(m);
        vis = VI(m);
        shuffle(all(back), rng);
        for (EDGE& e : back) {
            op[e.i] = true;
            VI vec{cnt};
            int mn = cnt;
            int mx = cnt;

            VI eget;
            bool tp1 = false;
            bool tp2 = false;
            for (int x : e.get()) {
                if (tp[x] == 0) {
                    eget.pb(x);
                } else if (tp[x] == 1) {
                    if (!tp1) {
                        eget.pb(x);
                        tp1 = true;
                    }
                } else {
                    if (!tp2) {
                        eget.pb(x);
                        tp2 = true;
                    }
                }
                /*eget.pb(x);*/
            }

            for (int x : eget) {
                op[x] = false;
                int cur = count_common_roads2(op);
                vec.pb(cur);
                setmin(mn, cur);
                setmax(mx, cur);
                op[x] = true;
            }
            if (mn == mx) {
                tp[e.i] = 1;
                for (int x : eget) {
                    tp[x] = 1;
                }
            } else {
                if (vec[0] == mn) tp[e.i] = 2;
                else tp[e.i] = 1;
                int ind = 1;
                for (int x : eget) {
                    if (vec[ind] == mn) tp[x] = 2;
                    else tp[x] = 1;
                    ind++;
                }
            }
            op[e.i] = false;
        }
        /*rep(u, m) if (!vis[u]) {*/
        /*    comp = VI();*/
        /*    dfs2(u);*/
        /*    int t = -1;*/
        /*    for (int u : comp) if (tp[u]) t = tp[u];*/
        /*    if (t == -1) break;*/
        /*    for (int u : comp) tp[u] = t;*/
        /*}*/
        VI ret;
        rep(i, m) if (tp[i] == 0) tp[i] = 2;
        rep(i, m) if (tp[i] == 2) ret.pb(i);
        return ret;
    }
}
namespace TEST4 {
    VPI edges;
    const int MAXN = 500;
    int n, m;
    int edgeind[MAXN][MAXN];
    int isgold[MAXN*(MAXN-1)/2];
    int count_common_forest(VI a) {
        VVI gp(n);
        for (int ind : a) {auto[u, v] = edges[ind];
            gp[u].pb(v);
            gp[v].pb(u);
        }
        VI vis(n);
        VI comp;
        function<void(int)> dfs;
        dfs = [&](int u) {
            comp.pb(u);
            vis[u] = true;
            for (int v : gp[u]) if (!vis[v]) dfs(v);
        };
        int change = 0;
        VI tmp(m);
        for (int ind : a) tmp[ind] = true;
        replr(u, 1, n-1) if (!vis[u]) {
            comp = VI();
            dfs(u);
            bool ka0 = false;
            for (int x : comp) if (x == 0) ka0 = true;
            if (ka0) continue;
            int ind = edgeind[0][comp[0]];
            tmp[ind] = true;
            change -= isgold[ind];
        }
        return count_common_roads2(tmp) + change;
    }
    VI solve(int N, VI U, VI V) {
        if (N == 2) return {0};
        n = N;
        m = n*(n-1)/2;
        rep(i, m) {
            isgold[i] = false;
            edgeind[U[i]][V[i]] = edgeind[V[i]][U[i]] = i;
            if (U[i] > V[i]) swap(U[i], V[i]);
            edges.pb({U[i], V[i]});
        }
        VI astx(m);
        replr(u, 1, n-1) astx[edgeind[0][u]] = true;
        int cnt1 = count_common_roads2(astx);
        replr(u, 1, n-1) {
            /*checking if edge 0..u is gold*/
            int v;
            if (u == 1) v = 2;
            else v = 1;
            astx[edgeind[0][v]] = false;
            astx[edgeind[v][u]] = true;
            int cnt2 = count_common_roads2(astx);
            astx[edgeind[0][v]] = true;
            astx[edgeind[0][u]] = false;
            int cnt3 = count_common_roads2(astx);
            astx[edgeind[0][u]] = true;
            astx[edgeind[v][u]] = false;
            if (cnt3 < cnt1 || cnt3 < cnt2) isgold[edgeind[0][u]] = true;
        }
        /*cout << "ASTXI VOSKE KOXER: " << endl;*/
        /*rep(i, m) if (isgold[i]) {*/
        /*    cout << edges[i].ff << " " << edges[i].ss << endl;*/
        /*}*/
        queue<int> leaf;
        VI degree(n);
        rep(u, n) {
            VI tmp;
            rep(v, n) if (v != u) {
                tmp.pb(edgeind[u][v]);
            }
            degree[u] = count_common_forest(tmp);
            if (degree[u] == 1) leaf.push(u);
        }
        /*rep(u, n) cout << "degree[" << u << "] = " << degree[u] << endl;*/
        /*cout << "SKSAV" << endl;*/
        VI ans;
        VI par(n, -1);
        while (leaf.size()) {
            int u = leaf.front();
            leaf.pop();
            if (degree[u] == 0) continue;
            VI e;
            rep(v, n) if (v != u && par[v] == -1) e.pb(v);
            auto f = [&](int m) {
                VI qr;
                replr(i, 0, m) {
                    qr.pb(edgeind[u][e[i]]);
                }
                return count_common_forest(qr);
            };
            int l = -1, r = e.size()-1;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                if (f(m)) r = m;
                else l = m;
            }
            par[u] = e[r];
            ans.pb(edgeind[u][par[u]]);
            /*cout << "par[" << u << "] = " << par[u] << endl;*/
            if (--degree[par[u]] == 1) leaf.push(par[u]);
        }

        return ans;
    }
};

VI find_roads(int N, VI U, VI V) {
    if (N <= 50) return TEST2::solve(N, U, V);
    return TEST4::solve(N, U, V);
}

Compilation message (stderr)

simurgh.cpp: In function 'bool TEST1::istree(VPI)':
simurgh.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for (auto[u, v] : edges) {
      |                  ^
simurgh.cpp: In function 'void TEST2::dfs(int, int, int)':
simurgh.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto[v, i] : gp[u]) if (i != pi) {
      |                  ^
simurgh.cpp: In function 'int TEST4::count_common_forest(VI)':
simurgh.cpp:219:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  219 |         for (int ind : a) {auto[u, v] = edges[ind];
      |                                ^

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