Submission #1259816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259816		Faggi	Simurgh (IOI17_simurgh)	C++20	0 / 100	11 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);
    do
    {
        vector<int> ars;
        bool con = 0;
        for (i = 0; i < sz(ord) - 1; i++)
        {
            if (pos[ord[i]][ord[i + 1]] == 0)
            {
                con = 1;
                break;
            }
            ars.pb(grafo[ord[i]][ord[i + 1]]);
            un[ord[i]][ord[i + 1]] = tim;
            un[ord[i + 1]][ord[i]] = tim;
        }
        if (dfs(ord[0]) == n)
            cant = count_common_roads(ars);
        tim++;
        cant=0;
        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]];
                }
                for(ll k=0; k<sz(ars); k++)
                {
                    un[inp[ars[k]].fr][inp[ars[k]].se]=tim;
                    un[inp[ars[k]].se][inp[ars[k]].fr]=tim;
                }
                if (dfs(ord[0]) == n)
                    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