Submission #1061568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061568		Zicrus	Simurgh (IOI17_simurgh)	C++17	13 / 100	1 ms	348 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

typedef long long ll;

vector<ll> lnk;

ll find(ll a) {
    if (lnk[a] != a) lnk[a] = find(lnk[a]);
    return lnk[a];
}

bool same(ll a, ll b) {
    return find(a) == find(b);
}

void unite(ll a, ll b) {
    a = find(a); b = find(b);
    lnk[a] = b;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();

    if (n == 7) {
        for (int i0 = 0; i0 < m; i0++) {
            for (int i1 = i0+1; i1 < m; i1++) {
                for (int i2 = i1+1; i2 < m; i2++) {
                    for (int i3 = i2+1; i3 < m; i3++) {
                        for (int i4 = i3+1; i4 < m; i4++) {
                            for (int i5 = i4+1; i5 < m; i5++) {
                                lnk = vector<ll>(n);
                                for (int i = 0; i < n; i++) lnk[i] = i;
                                if (same(u[i0], v[i0])) continue;
                                unite(u[i0], v[i0]);
                                if (same(u[i1], v[i1])) continue;
                                unite(u[i1], v[i1]);
                                if (same(u[i2], v[i2])) continue;
                                unite(u[i2], v[i2]);
                                if (same(u[i3], v[i3])) continue;
                                unite(u[i3], v[i3]);
                                if (same(u[i4], v[i4])) continue;
                                unite(u[i4], v[i4]);
                                if (same(u[i5], v[i5])) continue;
                                unite(u[i5], v[i5]);
                                ll val = count_common_roads({i0, i1, i2, i3, i4, i5});
                                if (val == 6) return {i0, i1, i2, i3, i4, i5};
                                if (val == 5) continue;
                                if (val == 4) break;
                                if (val == 3) goto nw3;
                                if (val == 2) goto nw4;
                                if (val == 1) goto nw5;
                                if (val == 0) goto nw6;
                            }
                            continue;
                            nw3:
                            break;
                        }
                        continue;
                        nw4:
                        break;
                    }
                    continue;
                    nw5:
                    break;
                }
                continue;
                nw6:
                break;
            }
        }
    }
    if (n == 6) {
        for (int i0 = 0; i0 < m; i0++) {
            for (int i1 = i0+1; i1 < m; i1++) {
                for (int i2 = i1+1; i2 < m; i2++) {
                    for (int i3 = i2+1; i3 < m; i3++) {
                        for (int i4 = i3+1; i4 < m; i4++) {
                            lnk = vector<ll>(n);
                            for (int i = 0; i < n; i++) lnk[i] = i;
                            if (same(u[i0], v[i0])) continue;
                            unite(u[i0], v[i0]);
                            if (same(u[i1], v[i1])) continue;
                            unite(u[i1], v[i1]);
                            if (same(u[i2], v[i2])) continue;
                            unite(u[i2], v[i2]);
                            if (same(u[i3], v[i3])) continue;
                            unite(u[i3], v[i3]);
                            if (same(u[i4], v[i4])) continue;
                            unite(u[i4], v[i4]);
                            ll val = count_common_roads({i0, i1, i2, i3, i4});
                            if (val == n-1) return {i0, i1, i2, i3, i4};
                        }
                    }
                }
            }
        }
    }
    if (n == 5) {
        for (int i0 = 0; i0 < m; i0++) {
            for (int i1 = i0+1; i1 < m; i1++) {
                for (int i2 = i1+1; i2 < m; i2++) {
                    for (int i3 = i2+1; i3 < m; i3++) {
                        lnk = vector<ll>(n);
                        for (int i = 0; i < n; i++) lnk[i] = i;
                        if (same(u[i0], v[i0])) continue;
                        unite(u[i0], v[i0]);
                        if (same(u[i1], v[i1])) continue;
                        unite(u[i1], v[i1]);
                        if (same(u[i2], v[i2])) continue;
                        unite(u[i2], v[i2]);
                        if (same(u[i3], v[i3])) continue;
                        unite(u[i3], v[i3]);
                        ll val = count_common_roads({i0, i1, i2, i3});
                        if (val == n-1) return {i0, i1, i2, i3};
                    }
                }
            }
        }
    }
    if (n == 4) {
        for (int i0 = 0; i0 < m; i0++) {
            for (int i1 = i0+1; i1 < m; i1++) {
                for (int i2 = i1+1; i2 < m; i2++) {
                    lnk = vector<ll>(n);
                    for (int i = 0; i < n; i++) lnk[i] = i;
                    if (same(u[i0], v[i0])) continue;
                    unite(u[i0], v[i0]);
                    if (same(u[i1], v[i1])) continue;
                    unite(u[i1], v[i1]);
                    if (same(u[i2], v[i2])) continue;
                    unite(u[i2], v[i2]);
                    ll val = count_common_roads({i0, i1, i2});
                    if (val == n-1) return {i0, i1, i2};
                }
            }
        }
    }
    if (n == 3) {
        for (int i0 = 0; i0 < m; i0++) {
            for (int i1 = i0+1; i1 < m; i1++) {
                lnk = vector<ll>(n);
                for (int i = 0; i < n; i++) lnk[i] = i;
                if (same(u[i0], v[i0])) continue;
                unite(u[i0], v[i0]);
                if (same(u[i1], v[i1])) continue;
                unite(u[i1], v[i1]);
                ll val = count_common_roads({i0, i1});
                if (val == n-1) return {i0, i1};
            }
        }
    }
    if (n == 2) {
        for (int i0 = 0; i0 < m; i0++) {
            lnk = vector<ll>(n);
            for (int i = 0; i < n; i++) lnk[i] = i;
            if (same(u[i0], v[i0])) continue;
            unite(u[i0], v[i0]);
            ll val = count_common_roads({i0});
            if (val == n-1) return {i0};
        }
    }
    
    return {};
}

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