oj.uz

Submission #228035

# Submission time Handle Problem Language Result Execution time Memory
228035 2020-04-29T15:35:56 Z AaronNaidu Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 384 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

int n;
vector<int> u, v;
vector<int> graph[600];
vector<int> subset, toRet;
bool visited[600];



void DFS(int node) {
    visited[node] = true;
    for (auto i : graph[node])
    {
        if (!visited[i])
        {
            DFS(i);
        }
        
    }
    
}

void getSubset(int used, int pos) {
    if (used == n-1)
    {
        for (auto i : subset)
        {
            graph[u[i]].push_back(v[i]);
            graph[v[i]].push_back(u[i]);
        }
        DFS(0);
        bool allRight = true;
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                allRight = false;
            }
        }
        if (allRight)
        {
            if (count_common_roads(subset) == n-1)
            {
                toRet = subset;
            }
        }
        for (int i = 0; i < n; i++)
        {
            visited[i] = false;
            graph[i].clear();
        }
        
        return;
    }

    if (pos >= u.size())
    {
        return;
    }
    
    for (int i = pos; i < u.size(); i++)
    {
        subset.push_back(i);
        getSubset(used+1, i+1);
        subset.pop_back();
    }
    
}

vector<int> find_roads(int ln, vector<int> lu, vector<int> lv) {
    n = ln;
    u = lu;
    v = lv;
    
    getSubset(0, 0);
    return toRet;
}

Compilation message

simurgh.cpp: In function 'void getSubset(int, int)':
simurgh.cpp:59:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= u.size())
         ~~~~^~~~~~~~~~~
simurgh.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = pos; i < u.size(); i++)
                       ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB correct
2 Correct 17 ms 384 KB correct
3 Correct 17 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 5 ms 384 KB correct
6 Correct 6 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 5 ms 384 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 5 ms 384 KB correct
12 Correct 5 ms 384 KB correct
13 Correct 18 ms 384 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB correct
2 Correct 17 ms 384 KB correct
3 Correct 17 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 5 ms 384 KB correct
6 Correct 6 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 5 ms 384 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 5 ms 384 KB correct
12 Correct 5 ms 384 KB correct
13 Correct 18 ms 384 KB correct
14 Execution timed out 3068 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB correct
2 Correct 17 ms 384 KB correct
3 Correct 17 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 5 ms 384 KB correct
6 Correct 6 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 5 ms 384 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 5 ms 384 KB correct
12 Correct 5 ms 384 KB correct
13 Correct 18 ms 384 KB correct
14 Execution timed out 3068 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB correct
2 Incorrect 75 ms 376 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB correct
2 Correct 17 ms 384 KB correct
3 Correct 17 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 5 ms 384 KB correct
6 Correct 6 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 5 ms 384 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 5 ms 384 KB correct
12 Correct 5 ms 384 KB correct
13 Correct 18 ms 384 KB correct
14 Execution timed out 3068 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -