oj.uz

Submission #1011348

# Submission time Handle Problem Language Result Execution time Memory
1011348 2024-06-30T12:01:01 Z c2zi6 Simurgh (IOI17_simurgh) C++14
49 / 100
 1764 ms 9404 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 508 KB correct
5 Correct 0 ms 352 KB correct
6 Correct 0 ms 352 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 508 KB correct
5 Correct 0 ms 352 KB correct
6 Correct 0 ms 352 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 608 KB correct
15 Correct 4 ms 604 KB correct
16 Correct 4 ms 600 KB correct
17 Correct 4 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 4 ms 348 KB correct
20 Correct 3 ms 348 KB correct
21 Correct 2 ms 348 KB correct
22 Correct 2 ms 348 KB correct
23 Correct 2 ms 348 KB correct
24 Correct 2 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 2 ms 348 KB correct
27 Correct 2 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 540 KB correct
31 Correct 2 ms 348 KB correct
32 Correct 2 ms 348 KB correct
33 Correct 2 ms 352 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 508 KB correct
5 Correct 0 ms 352 KB correct
6 Correct 0 ms 352 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 608 KB correct
15 Correct 4 ms 604 KB correct
16 Correct 4 ms 600 KB correct
17 Correct 4 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 4 ms 348 KB correct
20 Correct 3 ms 348 KB correct
21 Correct 2 ms 348 KB correct
22 Correct 2 ms 348 KB correct
23 Correct 2 ms 348 KB correct
24 Correct 2 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 2 ms 348 KB correct
27 Correct 2 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 540 KB correct
31 Correct 2 ms 348 KB correct
32 Correct 2 ms 348 KB correct
33 Correct 2 ms 352 KB correct
34 Correct 153 ms 2580 KB correct
35 Runtime error 7 ms 3800 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 409 ms 5780 KB correct
4 Correct 1730 ms 9144 KB correct
5 Correct 1764 ms 8708 KB correct
6 Correct 1668 ms 9404 KB correct
7 Correct 1592 ms 8836 KB correct
8 Correct 1647 ms 8708 KB correct
9 Correct 1642 ms 9268 KB correct
10 Correct 1640 ms 9332 KB correct
11 Correct 1746 ms 9280 KB correct
12 Correct 1675 ms 8832 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 1640 ms 8716 KB correct
15 Correct 1708 ms 9224 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 508 KB correct
5 Correct 0 ms 352 KB correct
6 Correct 0 ms 352 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 608 KB correct
15 Correct 4 ms 604 KB correct
16 Correct 4 ms 600 KB correct
17 Correct 4 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 4 ms 348 KB correct
20 Correct 3 ms 348 KB correct
21 Correct 2 ms 348 KB correct
22 Correct 2 ms 348 KB correct
23 Correct 2 ms 348 KB correct
24 Correct 2 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 2 ms 348 KB correct
27 Correct 2 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 540 KB correct
31 Correct 2 ms 348 KB correct
32 Correct 2 ms 348 KB correct
33 Correct 2 ms 352 KB correct
34 Correct 153 ms 2580 KB correct
35 Runtime error 7 ms 3800 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -