Submission #1259820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259820		Faggi	Simurgh (IOI17_simurgh)	C++20	0 / 100	0 ms	328 KiB

simurgh

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN = 501;

ll grafo[MAXN][MAXN], pos[MAXN][MAXN], un[MAXN][MAXN], tim = 1, vis[MAXN];
int count_common_roads(const vector<int> &r);

ll N;

ll dfs(ll nod)
{
    vis[nod] = tim;
    ll cant = 1;
    for (ll i = 0; i < N; i++)
    {
        if (un[nod][i] == tim && vis[i] != tim)
            cant += dfs(i);
    }
    return cant;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
    N = n;
    ll i, cant = 0, j, ma, pad, act;
    vector<pair<ll, ll>> inp;
    for (i = 0; i < sz(u); i++)
    {
        grafo[u[i]][v[i]] = i;
        grafo[v[i]][u[i]] = i;
        pos[u[i]][v[i]] = 1;
        pos[v[i]][u[i]] = 1;
        inp.pb({u[i], v[i]});
    }
    vector<int> ord;
    for (i = 0; i < n; i++)
        ord.pb(i);
    reverse(all(ord));
    do
    {
        vector<int> ars;
        bool con = 0, pu;
        for (i = 0; i < sz(ord) - 1; i++)
        {
            if (pos[ord[i]][ord[i + 1]] == 0)
            {
                pu = 0;
                for (j = 0; j < i; j++)
                {
                    if (pos[ord[j]][ord[i + 1]])
                    {
                        ars.pb(grafo[ord[j]][ord[i + 1]]);
                        pu = 1;
                        break;
                    }
                }
                if (pu == 0)
                {
                    con = 1;
                    break;
                }
            }
            else
                ars.pb(grafo[ord[i]][ord[i + 1]]);
        }
        if (con)
            continue;
        cant = count_common_roads(ars);
        tim++;
        if (cant == sz(ars))
            return ars;
        for (i = 1; i < sz(ord); i++)
        {
            ma = cant;
            pad = ord[i - 1];
            for (j = 0; j < i - 1; j++)
            {
                if (pos[ord[i]][ord[j]])
                {
                    ars[i - 1] = grafo[ord[i]][ord[j]];
                }
                act = count_common_roads(ars);
                tim++;
                if (act == sz(ars))
                    return ars;
                if (ma < act)
                {
                    ma = act;
                    pad = ord[j];
                }
            }
            cant = ma;
            ars[i - 1] = grafo[pad][i];
        }

    } while (next_permutation(all(ord)));
    return ord;
}

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