oj.uz

Submission #42951

# Submission time Handle Problem Language Result Execution time Memory
42951 2018-03-06T19:53:26 Z MatheusLealV Simurgh (IOI17_simurgh) C++14
13 / 100
 674 ms 876 KB 
#include <bits/stdc++.h>
#define N 505
#include "simurgh.h"
using namespace std;

int n, m;

int ok[N], pai[N];

vector<int> grafo[N];

int Find(int x)
{
    if(x == pai[x]) return x;

    return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
    a = Find(a), b = Find(b);

    if(a == b) return;

    pai[a] = b;
}

bool check(vector<int> vet, vector<int> &u, vector<int> &v)
{
    if(vet.size() != n - 1) return false;

    for(int i = 0; i < n; i++) pai[i] = i;

    for(auto x: vet)
    {
        join(u[x], v[x]);
    }

    set<int> ss;

    for(int i = 0; i < n; i++) ss.insert(Find(i));

    if(ss.size() != 1) return false;

    if(count_common_roads(vet) == n - 1) return true;

    else return false;
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v)
{
    n = n_;

    m = u.size();

    for(int i = 0; i < m; i++) grafo[u[i]].push_back(v[i]), grafo[v[i]].push_back(u[i]);

    for(int mask = 0; mask < (1<<m); mask ++)
    {
        vector<int> aux;

        for(int i = 0; i < m; i++)
        {
            if(mask & (1<<i))
            {
                aux.push_back(i);
            }
        }

        if(check(aux, u, v)) return aux;
    }

    return u;
}

Compilation message

simurgh.cpp: In function 'bool check(std::vector<int>, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vet.size() != n - 1) return false;
                   ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB correct
2 Correct 526 ms 456 KB correct
3 Correct 674 ms 588 KB correct
4 Correct 3 ms 608 KB correct
5 Correct 1 ms 608 KB correct
6 Correct 15 ms 616 KB correct
7 Correct 1 ms 632 KB correct
8 Correct 1 ms 756 KB correct
9 Correct 0 ms 756 KB correct
10 Correct 5 ms 772 KB correct
11 Correct 3 ms 772 KB correct
12 Correct 6 ms 772 KB correct
13 Correct 174 ms 864 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB correct
2 Correct 526 ms 456 KB correct
3 Correct 674 ms 588 KB correct
4 Correct 3 ms 608 KB correct
5 Correct 1 ms 608 KB correct
6 Correct 15 ms 616 KB correct
7 Correct 1 ms 632 KB correct
8 Correct 1 ms 756 KB correct
9 Correct 0 ms 756 KB correct
10 Correct 5 ms 772 KB correct
11 Correct 3 ms 772 KB correct
12 Correct 6 ms 772 KB correct
13 Correct 174 ms 864 KB correct
14 Incorrect 4 ms 876 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB correct
2 Correct 526 ms 456 KB correct
3 Correct 674 ms 588 KB correct
4 Correct 3 ms 608 KB correct
5 Correct 1 ms 608 KB correct
6 Correct 15 ms 616 KB correct
7 Correct 1 ms 632 KB correct
8 Correct 1 ms 756 KB correct
9 Correct 0 ms 756 KB correct
10 Correct 5 ms 772 KB correct
11 Correct 3 ms 772 KB correct
12 Correct 6 ms 772 KB correct
13 Correct 174 ms 864 KB correct
14 Incorrect 4 ms 876 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB correct
2 Incorrect 6 ms 876 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 248 KB correct
2 Correct 526 ms 456 KB correct
3 Correct 674 ms 588 KB correct
4 Correct 3 ms 608 KB correct
5 Correct 1 ms 608 KB correct
6 Correct 15 ms 616 KB correct
7 Correct 1 ms 632 KB correct
8 Correct 1 ms 756 KB correct
9 Correct 0 ms 756 KB correct
10 Correct 5 ms 772 KB correct
11 Correct 3 ms 772 KB correct
12 Correct 6 ms 772 KB correct
13 Correct 174 ms 864 KB correct
14 Incorrect 4 ms 876 KB WA in grader: NO
15 Halted 0 ms 0 KB -