oj.uz

Submission #656239

# Submission time Handle Problem Language Result Execution time Memory
656239 2022-11-06T15:41:05 Z Hydroxic_Acid Logičari (COCI21_logicari) C++17
10 / 110
 1000 ms 10824 KB 
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int N;
vector<int> adjl[100005];
bool visited[100005];
int see[100005];
int cnt = 0;

int dp(int i){
    if(i <= N){
        cnt++;
        for(int j = 0; j < (int)adjl[i].size(); j++){
            see[adjl[i][j]]++;
        }
        int returnval = dp(i + 1);
        cnt--;
        for(int j = 0; j < (int)adjl[i].size(); j++){
            see[adjl[i][j]]--;
        }
        int temp = dp(i + 1);
        if(temp == -1) return returnval;
        if(returnval == -1) return temp;
        return min(returnval, temp);
    }
    for(int j = 1; j <= N; j++){
        if(see[j] != 1) return -1;
    }
    return cnt;
}

int main(){
    cin >> N;

    for(int i = 0; i < N; i++){
        int a, b; cin >> a >> b;
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }

    memset(visited, false, sizeof(visited));
    memset(see, 0, sizeof(see));

    cout << dp(1);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Execution timed out 1084 ms 10824 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 15 ms 3136 KB Output is correct
3 Correct 19 ms 3036 KB Output is correct
4 Correct 19 ms 3144 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 9 ms 3136 KB Output is correct
7 Correct 2 ms 3040 KB Output is correct
8 Correct 6 ms 3044 KB Output is correct
9 Correct 64 ms 3028 KB Output is correct
10 Correct 44 ms 3028 KB Output is correct
11 Correct 4 ms 3040 KB Output is correct
12 Correct 17 ms 3028 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 15 ms 3136 KB Output is correct
3 Correct 19 ms 3036 KB Output is correct
4 Correct 19 ms 3144 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 9 ms 3136 KB Output is correct
7 Correct 2 ms 3040 KB Output is correct
8 Correct 6 ms 3044 KB Output is correct
9 Correct 64 ms 3028 KB Output is correct
10 Correct 44 ms 3028 KB Output is correct
11 Correct 4 ms 3040 KB Output is correct
12 Correct 17 ms 3028 KB Output is correct
13 Execution timed out 1080 ms 3156 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Execution timed out 1084 ms 10824 KB Time limit exceeded
6 Halted 0 ms 0 KB -