Submission #117775

#	Time	Username	Problem	Language	Result	Execution time	Memory
117775		Plurm	Simurgh (IOI17_simurgh)	C++14	0 / 100	3 ms	640 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > g[512];
int par[512];
int pare[512];
vector<int> cycle;
void dfs(int u, int p = -1){
    for(auto v : g[u]){
        if(v.first == p) continue;
        if(par[v.first] != -1){
            // Cycle is found!
            if(cycle.empty()){
                // First cycle found. Use it.
                int x = u;
                cycle.push_back(v.second);
                while(x != v.first){
                    cycle.push_back(pare[x]);
                    x = par[x];
                }
            }
        }else{
            pare[v.first] = v.second;
            par[v.first] = u;
            dfs(v.first, u);
        }
    }
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    for(int i = 0; i < m; i++){
        g[u[i]].emplace_back(v[i],i);
        g[v[i]].emplace_back(u[i],i);
    }
    do{
        memset(par, -1, sizeof(par));
        memset(pare, 0, sizeof(pare));
        cycle.clear();
        par[0] = -2;
        dfs(0);
        vector<int> r;
        for(int i = 1; i < n; i++){
            r.push_back(pare[i]);
        }
        int ret = count_common_roads(r);
        if(ret == n-1) return r;
        int mx = -1;
        int mindex = -1;
        if(ret > mx){
            mx = ret;
            mindex = 0;
        }
        for(int i = 1; i < cycle.size(); i++){
            r.erase(find(r.begin(), r.end(), cycle[i]));
            r.push_back(cycle[i-1]);
            ret = count_common_roads(r);
            if(ret == n-1) return r;
            if(ret > mx){
                mx = ret;
                mindex = i;
            }
        }
        u.erase(u.begin()+cycle[mindex]);
        v.erase(v.begin()+cycle[mindex]);
    }while(!cycle.empty());
    vector<int> r;
    for(int i = 1; i < n; i++){
        r.push_back(pare[i]);
    }
    return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:53:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < cycle.size(); i++){
                        ~~^~~~~~~~~~~~~~

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