Submission #428974

#	Time	Username	Problem	Language	Result	Execution time	Memory
428974		Dremix10	Simurgh (IOI17_simurgh)	C++17	13 / 100	3053 ms	7372 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+1;
const ll INF = 2e18;
const int MOD = 1e9+7;


vector<vector<pi> > a(N);
bool vs[N],idx[N];
int cnt;

void dfs(int s){
    cnt++;
    vs[s] = true;
    for(auto x : a[s])
    if(!vs[x.F] && idx[x.S])
        dfs(x.F);
}
int mm,nn;
vector<int> ans;

void solve(int curr, int last){
    if(curr == nn-1){
        cnt = 0;
        dfs(0);

        for(int i=0;i<nn;i++)
            vs[i] = false;
        vector<int> arr;
        for(int i=0;i<mm;i++)
            if(idx[i]){
                arr.push_back(i);
                //cout<<i<<" ";
            }//cout<<endl;
        //cout<<cnt<<endl;
        if(cnt != nn)return;

        if(count_common_roads(arr) == nn-1){
            ans = arr;
            return;
        }
    }
    for(int i=last+1;i<mm;i++){
        if(idx[i])continue;
        idx[i] = true;
        solve(curr+1,i);
        idx[i] = false;
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int i,j;
    mm = u.size();
    nn = n;

    for(i=0;i<mm;i++){
        int x = u[i];
        int y = v[i];
        a[x].push_back({y,i});
        a[y].push_back({x,i});
    }
    solve(0,-1);
    return ans;

}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:60:11: warning: unused variable 'j' [-Wunused-variable]
   60 |     int i,j;
      |           ^

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