제출 #1259812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259812		Faggi	Simurgh (IOI17_simurgh)	C++20	0 / 100	0 ms	324 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];
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, cant=0, j, ma, pad, act;
	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;
    }
    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]]);
        }
        if(con)
            continue;
        cant=count_common_roads(ars);
        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);
                if(act==sz(ars))
                    return ars;
                if(ma<act)
                {
                    ma=act;
                    pad=ord[j];
                }
            }
            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