Submission #1259824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259824		Faggi	Simurgh (IOI17_simurgh)	C++20	13 / 100	13 ms	580 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];

int count_common_roads(const vector<int> &r);
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
    ll i, j, act;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            grafo[i][j]=-1;
    for(i=0; i<sz(u); i++)
    {
        grafo[u[i]][v[i]]=i;
        grafo[v[i]][u[i]]=i;
    }
    vector<int>ord;
    for(i=0; i<n; i++)
        ord.pb(i);
    do
    {
        vector<int>ars(n-1,-1),pads(n-1,-1);
        for(i=1; i<n; i++)
        {
            for(j=i-1; j>=0; j--)
            {
                if(grafo[ord[i]][ord[j]]!=-1)
                {
                    ars[i-1]=grafo[ord[i]][ord[j]];
                    pads[i-1]=ord[j];
                    break;
                }
            }
            if(ars[i-1]==-1)
                break;
        }
        if(ars[n-2]==-1)
            continue;

        ll cant=count_common_roads(ars);
        if(cant==n-1)
            return ars;
        for(i=1; i<n; i++)
        {
            ll ma=cant, pad=pads[i-1], ar=ars[i-1];
            for(j=i-1; j>=0; j--)
            {
                if(grafo[ord[i]][ord[j]]!=-1)
                {
                    ars[i-1]=grafo[ord[i]][ord[j]];
                    pads[i-1]=ord[j];
                    act=count_common_roads(ars);
                    if(act>ma)
                    {
                        ma=act;
                        pad=ord[j];
                        ar=grafo[ord[i]][ord[j]];
                    }
                }
            }
            pads[i-1]=pad;
            ars[i-1]=ar;
            cant=ma;
        }
        if(cant==n-1)
            return ars;
    }while(next_permutation(all(ord)));
    return ord;
}

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