oj.uz

Submission #117775

# Submission time Handle Problem Language Result Execution time Memory
117775 2019-06-17T07:50:44 Z Plurm Simurgh (IOI17_simurgh) C++14
0 / 100
 3 ms 640 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -