oj.uz

Submission #584482

# Submission time Handle Problem Language Result Execution time Memory
584482 2022-06-27T12:56:52 Z PiejanVDC Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 304 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

int count_common_roads(const vector<int>& r);


vector<int>par;

int UF(int u) {
    if(par[u] == u)
        return u;
    return par[u] = UF(par[u]);
}

vector<int> find_roads(int n, vector<int>u, vector<int>v) {
    int m = u.size();

    par.resize(n);

    auto P = [&] () {
        for(int i = 0 ; i < n ; i++)
            par[i] = i;
    };

    auto splay = [&] (int a) {
        vector<int>ret;
        for(int i = 0 ; i < m ; i++) {
            if(a & (1 << i))
                ret.push_back(i);
        }
        return ret;
    };

    auto tree = [&] (vector<int>a) {
        P();
        if((int)a.size() != n-1)
            return 0;
        for(auto z : a) {
            int A = UF(u[z]), B = UF(v[z]);
            if(A == B)
                return 0;
            par[A] = B;
        }
        return 1;
    };

    for(int mask = 0 ; mask < (1 << m) ; mask++) {
        if(tree(splay(mask))) {
            vector<int>ask = splay(mask);
            int x = count_common_roads(ask);
            if(x == n-1) {
                return ask;
            }
        }
    }
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 212 KB correct
2 Correct 281 ms 280 KB correct
3 Correct 349 ms 280 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 8 ms 300 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 3 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 106 ms 280 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 212 KB correct
2 Correct 281 ms 280 KB correct
3 Correct 349 ms 280 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 8 ms 300 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 3 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 106 ms 280 KB correct
14 Execution timed out 3064 ms 304 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 212 KB correct
2 Correct 281 ms 280 KB correct
3 Correct 349 ms 280 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 8 ms 300 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 3 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 106 ms 280 KB correct
14 Execution timed out 3064 ms 304 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 212 KB correct
2 Correct 281 ms 280 KB correct
3 Correct 349 ms 280 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 8 ms 300 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 3 ms 212 KB correct
11 Correct 1 ms 300 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 106 ms 280 KB correct
14 Execution timed out 3064 ms 304 KB Time limit exceeded
15 Halted 0 ms 0 KB -