oj.uz

Submission #1043497

# Submission time Handle Problem Language Result Execution time Memory
1043497 2024-08-04T10:10:42 Z Zicrus Werewolf (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -