oj.uz

Submission #777991

# Submission time Handle Problem Language Result Execution time Memory
777991 2023-07-10T01:24:38 Z Magikarp4000 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 29692 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+5;
vector<int> v[MAXN];
int n,m,Q;
bool z[MAXN], z1[MAXN];

void reset() {
    FOR(i,0,n) {
        z[i] = z1[i] = 0;
    }
}

bool solve(int sta, int en, int l, int r) {
    queue<int> q;
    q.push(sta);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        z[s] = 1;
        FORX(u,v[s]) {
            if (z[u] || u < l) continue;
            q.push(u);
        }
    }
    q.push(en);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        z1[s] = 1;
        FORX(u,v[s]) {
            if (z1[u] || u > r) continue;
            q.push(u);
        }
    }
    FOR(i,0,n) if (z[i] && z1[i]) return 1;
    return 0;
}

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) {
    n = N, m = X.size(), Q = S.size();
    FOR(i,0,m) {
        v[X[i]].PB(Y[i]);
        v[Y[i]].PB(X[i]);
    }
    vector<int> res;
    FOR(i,0,Q) {
        reset();
        bool ans = solve(S[i],E[i],L[i],R[i]);
        res.PB(ans);
    }
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 305 ms 5480 KB Output is correct
11 Correct 98 ms 5360 KB Output is correct
12 Correct 15 ms 5376 KB Output is correct
13 Correct 318 ms 5348 KB Output is correct
14 Correct 123 ms 5360 KB Output is correct
15 Correct 508 ms 5484 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 305 ms 5480 KB Output is correct
11 Correct 98 ms 5360 KB Output is correct
12 Correct 15 ms 5376 KB Output is correct
13 Correct 318 ms 5348 KB Output is correct
14 Correct 123 ms 5360 KB Output is correct
15 Correct 508 ms 5484 KB Output is correct
16 Execution timed out 4062 ms 29692 KB Time limit exceeded
17 Halted 0 ms 0 KB -