oj.uz

Submission #599685

# Submission time Handle Problem Language Result Execution time Memory
599685 2022-07-19T18:51:51 Z skittles1412 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 32172 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using vi = vector<int>;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) {
    int m = sz(us), q = sz(qsrc);
    if (n <= 3000 && m <= 6000 && q <= 3000) {
        vector<int> graph[n];
        for (int i = 0; i < m; i++) {
            graph[us[i]].push_back(vs[i]);
            graph[vs[i]].push_back(us[i]);
        }
        vector<int> ans(q);
        for (int qi = 0; qi < q; qi++) {
            int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
            bool vis[n][2] {};
            vector<pair<int, int>> q;
            auto push = [&](int u, int t) -> void {
                if (!vis[u][t]) {
                    vis[u][t] = true;
                    q.emplace_back(u, t);
                }
            };
            push(src, 0);
            while (sz(q)) {
                auto [u, t] = q.back();
                q.pop_back();
                if (l <= u && u <= r && !t) {
                    push(u, 1);
                }
                for (auto& v : graph[u]) {
                    if ((!t && v >= l) || (t && v <= r)) {
                        push(v, t);
                    }
                }
            }
            ans[qi] = vis[dest][1];
        }
        return ans;
    }
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 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 268 ms 732 KB Output is correct
11 Correct 165 ms 704 KB Output is correct
12 Correct 16 ms 772 KB Output is correct
13 Correct 226 ms 740 KB Output is correct
14 Correct 147 ms 724 KB Output is correct
15 Correct 191 ms 840 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 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 268 ms 732 KB Output is correct
11 Correct 165 ms 704 KB Output is correct
12 Correct 16 ms 772 KB Output is correct
13 Correct 226 ms 740 KB Output is correct
14 Correct 147 ms 724 KB Output is correct
15 Correct 191 ms 840 KB Output is correct
16 Execution timed out 4077 ms 32172 KB Time limit exceeded
17 Halted 0 ms 0 KB -