oj.uz

답안 #1043497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043497 2024-08-04T10:10:42 Z Zicrus 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 21644 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

typedef long long ll;

ll n, m, q;
vector<vector<ll>> adj;

bool solve(ll s, ll e, ll l, ll r) {
    queue<ll> q;
    q.push(s);
    vector<bool> vstH(n), vstW(n);
    while (!q.empty()) {
        ll node = q.front(); q.pop();
        if (vstH[node]) continue;
        vstH[node] = true;
        for (auto &e : adj[node]) {
            if (e < l) continue;
            q.push(e);
        }
    }
    q.push(e);
    while (!q.empty()) {
        ll node = q.front(); q.pop();
        if (vstH[node]) return true;
        if (vstW[node]) continue;
        vstW[node] = true;
        for (auto &e : adj[node]) {
            if (e > r) continue;
            q.push(e);
        }
    }
    return false;
}

vector<int> check_validity(int n1, vector<int> x, vector<int> y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
    n = n1; m = x.size(); q = S.size();
    adj = vector<vector<ll>>(n);
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

    vector<int> res(q);
    while (q--) {
        ll s = S[q], e = E[q];
        ll l = L[q], r = R[q];
        res[q] = solve(s, e, l, r);
    }
    return res;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 105 ms 900 KB Output is correct
11 Correct 62 ms 856 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 103 ms 892 KB Output is correct
14 Correct 66 ms 860 KB Output is correct
15 Correct 135 ms 1036 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1706 ms 21644 KB Output is correct
2 Execution timed out 4072 ms 21536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 105 ms 900 KB Output is correct
11 Correct 62 ms 856 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 103 ms 892 KB Output is correct
14 Correct 66 ms 860 KB Output is correct
15 Correct 135 ms 1036 KB Output is correct
16 Correct 1706 ms 21644 KB Output is correct
17 Execution timed out 4072 ms 21536 KB Time limit exceeded
18 Halted 0 ms 0 KB -