Submission #359839

#	Time	Username	Problem	Language	Result	Execution time	Memory
359839		juggernaut	Simurgh (IOI17_simurgh)	C++14	30 / 100	392 ms	3692 KiB

simurgh

#include"simurgh.h"
#ifndef EVAL
#include"grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
int g[55][55],good[3025],n,used[55];
vector<int>cur;
void init(int v){
    used[v]=1;
    for(int i=0;i<n;i++)
        if(!used[i]&&g[v][i]>=0){
            cur.push_back(g[v][i]);
            init(i);
        }
}
void dfs(int v){
    used[v]=1;
    for(int i=0;i<n;i++)
        if(used[i]==0&&g[v][i]>=0&&good[g[v][i]]==1)dfs(i);
}
bool check(){
    memset(used,0,sizeof(used));
    memset(good,0,sizeof(good));
    for(int i:cur)good[i]=1;
    dfs(0);
    for(int i=0;i<n;i++)
        if(used[i]==0)return 0;
    return 1;
}
vector<int>find_roads(int N,vector<int>u,vector<int>v){
    n=N;
    int m=u.size();
    memset(g,-1,sizeof(g));
    for(int i=0;i<m;i++)g[u[i]][v[i]]=g[v[i]][u[i]]=i;
    init(0);
    while(true){
        int now=count_common_roads(cur);
        if(now==n-1)return cur;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m;j++){
                if(cur[i]!=j){
                    int old=cur[i];
                    cur[i]=j;
                    if(check()){
                        int temp=count_common_roads(cur);
                        if(temp>now)now=temp;
                        else cur[i]=old;
                    }else cur[i]=old;
                }
            }
        }
    }
}

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