oj.uz

Submission #1092441

# Submission time Handle Problem Language Result Execution time Memory
1092441 2024-09-24T06:17:08 Z huyngo Werewolf (IOI18_werewolf) C++17
15 / 100
 173 ms 29780 KB 
#include "werewolf.h"
#include <bits/stdc++.h>  
using namespace std;
using ll = long long;
using i64 = long long;
void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char* x) { cerr << '"' << x << '"'; } void __print(const string& x) { cerr << '"' << x << '"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template<typename T, typename V> void __print(const pair<T, V>& x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; } template<typename T> void __print(const T& x) { int f = 0; cerr << '{'; for (auto& i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#define ln "\n"
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define ar array
int Bit(int mask, int b) { return (mask >> b) & 1; }
const ll base = 311, MOD = 998244353, M = 1e9 + 7, INF = 1e18;

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 Q = S.size();
    int M = X.size();
    std::vector<int> ANS(Q);

    vector<vector<int>> adj(N);
    rep(i, 0, M - 1) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    if (N <= 3000) {
        rep(i, 0, Q - 1) {
            vector<int> vis(N, 0);
            int ok = 0;
            auto dfs = [&](auto self, int u, int lb, int ub) -> void {
                if (u < lb || u > ub) return;
                vis[u] = (ub == 1e8 ? 1 : 2);
                for (int v : adj[u])
                    if (!vis[v]) {
                        if (lb <= v && v <= ub)
                            self(self, v, lb, ub);
                    }
                    else {
                        if (lb == -1 && vis[v] == 1 && v <= R[i])
                            ok = 1;
                    }
                };
            dfs(dfs, S[i], L[i], 1e8);
            if (E[i] <= R[i] && vis[E[i]] == 1)
                ok = true;
            dfs(dfs, E[i], -1, R[i]);
            ANS[i] = ok;
        }
    }
    return ANS;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 138 ms 912 KB Output is correct
11 Correct 70 ms 856 KB Output is correct
12 Correct 9 ms 860 KB Output is correct
13 Correct 173 ms 860 KB Output is correct
14 Correct 122 ms 860 KB Output is correct
15 Correct 163 ms 1088 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 29780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 138 ms 912 KB Output is correct
11 Correct 70 ms 856 KB Output is correct
12 Correct 9 ms 860 KB Output is correct
13 Correct 173 ms 860 KB Output is correct
14 Correct 122 ms 860 KB Output is correct
15 Correct 163 ms 1088 KB Output is correct
16 Incorrect 126 ms 29780 KB Output isn't correct
17 Halted 0 ms 0 KB -