oj.uz

Submission #434432

# Submission time Handle Problem Language Result Execution time Memory
434432 2021-06-21T09:46:40 Z dxz05 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 36716 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

vector<int> g[MAXN];

void dfs(int v, int l, int r, vector<bool> &used){
    used[v] = true;

    for (int u : g[v]){
        if (!used[u] && l <= u && u <= r){
            dfs(u, l, r, used);
        }
    }

}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = S.size(), M = X.size();
    vector<int> A(Q, 0);

    for (int i = 0; i < M; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < Q; i++){
        vector<bool> used1(N, false), used2(N, false);
        dfs(S[i], L[i], N - 1, used1);
        dfs(E[i], 0, R[i], used2);

        for (int j = L[i]; j <= R[i]; j++){
            if (used1[j] && used2[j]) A[i] = 1;
        }

    }

    return A;
}

/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 11 ms 9684 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 11 ms 9684 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 293 ms 9964 KB Output is correct
11 Correct 194 ms 9928 KB Output is correct
12 Correct 27 ms 10116 KB Output is correct
13 Correct 337 ms 9976 KB Output is correct
14 Correct 214 ms 9932 KB Output is correct
15 Correct 270 ms 10076 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 11 ms 9684 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9696 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 293 ms 9964 KB Output is correct
11 Correct 194 ms 9928 KB Output is correct
12 Correct 27 ms 10116 KB Output is correct
13 Correct 337 ms 9976 KB Output is correct
14 Correct 214 ms 9932 KB Output is correct
15 Correct 270 ms 10076 KB Output is correct
16 Execution timed out 4059 ms 36716 KB Time limit exceeded
17 Halted 0 ms 0 KB -