Submission #1065532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065532		TheQuantiX	Simurgh (IOI17_simurgh)	C++17	51 / 100	189 ms	5676 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector<ll> G[500];

struct dsu {
    ll n;
    vector<ll> par;
    vector<ll> sz;

    dsu(ll N) : n(N) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    ll find_p(ll x) {
        if (par[x] == x) {
            return x;
        }
        ll p = find_p(par[x]);
        par[x] = p;
        return p;
    }

    void join(ll x, ll y) {
        x = find_p(x);
        y = find_p(y);
        if (x == y) {
            return;
        }
        if (sz[y] > sz[x]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
    mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
    n = N;
    m = u.size();
    vector< pair< pair<ll, ll>, ll > > vp(m);
    for (int i = 0; i < m; i++) {
        vp[i].first = {u[i], v[i]};
        vp[i].second = i;
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
    }
    map<int, int> ans;
    for (int i = 0; i < n; i++) {
        // cout << i << endl;
        for (int j = 0; j < m; j++) {
            swap(vp[j], vp[gen() % (j + 1)]);
        }
        dsu d(n);
        set<ll> st1, st2;
        vector<int> e;
        for (int j = 0; j < m; j++) {
            if (vp[j].first.first == i || vp[j].first.second == i) {
                if (ans.count(vp[j].second)) {
                    st2.insert(vp[j].second);
                }
                else {
                    st1.insert(vp[j].second);
                }
                continue;
            }
            if (d.find_p(vp[j].first.first) != d.find_p(vp[j].first.second)) {
                d.join(vp[j].first.first, vp[j].first.second);
                e.push_back(vp[j].second);
            }
        }
        if (st1.size() == 0) {
            continue;
        }
        // cout << st1.size() << ' ' << st2.size() << endl;
        set<ll> st;
        map<ll, ll> to;
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            st.insert(d.find_p(j));
        }
        ll cnt = 0;
        for (auto j : st) {
            to[j] = cnt++;
        }
        vector< vector<ll> > v1(cnt), v2(cnt);
        for (int j : st1) {
            v1[to[d.find_p(v[j] != i ? v[j] : u[j])]].push_back(j);
        }
        for (int j : st2) {
            v2[to[d.find_p(v[j] != i ? v[j] : u[j])]].push_back(j);
        }
        for (int j = cnt - 1; j >= 0; j--) {
            e.push_back((v1[j].size() == 0) ? v2[j][0] : v1[j][0]);
        }
        reverse(e.begin(), e.end());
        // cout << "DEBUG" << endl;
        for (int i = 0; i < cnt; i++) {
            // cout << v1[i].size() << ' ' << v2[i].size() << '\n';
            if (v1[i].size() == 0) {
                continue;
            }
            map< ll, vector<ll> > mp;
            for (int j : v1[i]) {
                e[i] = j;
                mp[count_common_roads(e)].push_back(j);
            }
            if (mp.size() == 1) {
                if (v2[i].size() == 0) {
                    for (auto j : (*mp.begin()).second) {
                        ans[j] = 1;
                    }
                }
                else {
                    // cout << "DEBUG" << endl;
                    e[i] = v2[i][0];
                    ll x = count_common_roads(e);
                    for (auto j : mp) {
                        // cout << '\t' << j.first << ' ' << x << '\n';
                        for (auto k : j.second) {
                            // cout << "\t\t" << k << '\t';
                            if (j.first == x) {
                                ans[k] = ans[v2[i][0]];
                            }
                            else {
                                ans[k] = 1 - ans[v2[i][0]];
                            }
                            // cout << "\t\t" << ans[k] << '\n';
                        }
                    }
                }
            }
            else {
                for (auto i : (*mp.begin()).second) {
                    ans[i] = 0;
                }
                for (auto i : (*++mp.begin()).second) {
                    ans[i] = 1;
                }
            }
            e[i] = ((v1[i].size() == 0) ? v2[i][0] : v1[i][0]);
        }
    }
    vector<int> ansv;
    for (int i = 0; i < m; i++) {
        if (ans[i] == 1) {
            ansv.push_back(i);  
            // cout << i << ' ';
        }
    }
    // cout << '\n';
    return ansv;
}

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