oj.uz

Submission #283765

# Submission time Handle Problem Language Result Execution time Memory
283765 2020-08-26T07:03:37 Z 2qbingxuan Simurgh (IOI17_simurgh) C++14
0 / 100
 3000 ms 256 KB 
#include "simurgh.h"

#include <bits/stdc++.h>
#ifdef local
#define debug(...) QQBX(#__VA_ARGS__, __VA_ARGS__)
void QQBX(const char *s) {}
template <typename H, typename ...T> void QQBX(const char *s, const H&h, T &&...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if(sizeof...(T)) QQBX(++s, args...);
}
#define safe std::cerr<<__PRETTY_FUNCTION<<" line "<<__LINE__<<" safe\n";
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
const int N = 10025;

int pa[N], rk[N];
int anc(int x) { return x==pa[x] ? x : pa[x]=anc(pa[x]); }
bool join(int x, int y) {
    if((x=anc(x)) == (y=anc(y))) return false;
    if(rk[x] < rk[y]) swap(x, y);
    return pa[y] = x, rk[x]!=rk[y]||++rk[x], true;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    auto ok = [&](const vector<int> &ids) -> bool {
        assert(ids.size() == n-1);
        for(int i = 0; i < n; i++) pa[i] = i, rk[i] = 0;
        for(int x: ids) if(!join(u[x], v[x])) return false;
        return true;
    };
    int m = u.size();
    vector<int> r(m);
    iota(r.begin(), r.end(), 0);
    do {
        vector<int> q(r.begin(), r.begin()+n-1);
        if(ok(q) && count_common_roads(q) == n-1) return q;
    } while(next_permutation(r.begin(), r.end()));
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from simurgh.cpp:3:
simurgh.cpp: In lambda function:
simurgh.cpp:31:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         assert(ids.size() == n-1);
      |                ~~~~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:37:20: warning: control reaches end of non-void function [-Wreturn-type]
   37 |     vector<int> r(m);
      |                    ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Execution timed out 3081 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -