oj.uz

답안 #588505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588505 2022-07-03T12:19:02 Z georgievskiy 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 41884 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

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

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
        std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {

    int m = X.size(), q = S.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
        g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
    vector<int> u1(n), u2(n);
    vector<int> ans(q, 0);
    for (int i = 0; i < q; i++) {
        fill(u1.begin(), u1.end(), 0); fill(u2.begin(), u2.end(), 0);
        dfs(S[i], g, u1, L[i], n);
        dfs(E[i], g, u2, 0, R[i]);
        for (int v = 0; v < n; v++) {
            if (u1[v] && u2[v]) {
                ans[i] = 1;
                break;
            }
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 229 ms 776 KB Output is correct
11 Correct 128 ms 728 KB Output is correct
12 Correct 19 ms 912 KB Output is correct
13 Correct 251 ms 768 KB Output is correct
14 Correct 160 ms 724 KB Output is correct
15 Correct 236 ms 940 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4035 ms 41884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 229 ms 776 KB Output is correct
11 Correct 128 ms 728 KB Output is correct
12 Correct 19 ms 912 KB Output is correct
13 Correct 251 ms 768 KB Output is correct
14 Correct 160 ms 724 KB Output is correct
15 Correct 236 ms 940 KB Output is correct
16 Execution timed out 4035 ms 41884 KB Time limit exceeded
17 Halted 0 ms 0 KB -