oj.uz

Submission #738164

# Submission time Handle Problem Language Result Execution time Memory
738164 2023-05-08T08:26:59 Z danikoynov Werewolf (IOI18_werewolf) C++14
49 / 100
 800 ms 64392 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 10;

struct query
{
    int l, r, s, e;

    query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
    {
        l = _l;
        r = _r;
        s = _s;
        e = _e;
    }
} ask[maxn];

int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];

void bfs0(int v, int l)
{
    if (v < l)
        return;

    used0[v] = 1;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int u : graph[cur])
        {
            if (u < l)
                continue;
            if (used0[u] == 0)
            {
                q.push(u);
                used0[u] = 1;
            }
        }
    }
}

void bfs1(int v, int r)
{
    if (v > r)
        return;

    used1[v] = 1;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int u : graph[cur])
        {
            if (u > r)
                continue;
            if (used1[u] == 0)
            {
                q.push(u);
                used1[u] = 1;
            }
        }
    }
}


int solve_query(query cur)
{
    for (int i = 0; i < n; i ++)
    {
        used0[i] = used1[i] = 0;
    }

    bfs0(cur.s, cur.l);
    bfs1(cur.e, cur.r);

    for (int i = 0; i < n; i ++)
    {
        if (used0[i] == 1 && used1[i] == 1)
            return 1;
    }
    return 0;
}

int chain[maxn], pos, chain_idx[maxn];
void make_chain(int v, int bef)
{
    chain[++ pos] = v;
    chain_idx[v] = pos;
    for (int u : graph[v])
    {
        if (u == bef)
            continue;
        make_chain(u, v);
    }
}

struct node
{
    int max_num, min_num;

    node(int _max_num = -1e9, int _min_num = 1e9)
    {
        max_num = _max_num;
        min_num = _min_num;
    }
};


node tree[4 * maxn];

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = node(chain[left], chain[right]);
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root].max_num = max(tree[root * 2].max_num, tree[root * 2 + 1].max_num);
    tree[root].min_num = min(tree[root * 2].min_num, tree[root * 2 + 1].min_num);
}

int rightmost_lower(int root, int left, int right,
                    int qleft, int qright, int val)
{
    ///cout << "here " << left << " " << right << " " << val << " " << tree[root].min_num << " " << qleft << " " << qright <<  endl;
    if (left > qright || right < qleft ||
            tree[root].min_num >= val)
        return 0;

    if (left == right)
        return left;

    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2 + 1].min_num < val)
            return rightmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return rightmost_lower(root * 2, left, mid, qleft, qright, val);
    }

    return max(rightmost_lower(root * 2, left, mid, qleft, qright, val),
               rightmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int leftmost_lower(int root, int left, int right,
                   int qleft, int qright, int val)
{
    ///cout << "here " << left << " " << right << " " << val << " " << tree[root].min_num << " " << qleft << " " << qright <<  endl;
    if (left > qright || right < qleft ||
            tree[root].min_num >= val)
        return n + 1;

    if (left == right)
        return left;
    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        ///cout << tree[root * 2].min_num << endl;
        if (tree[root * 2].min_num < val)
            return leftmost_lower(root * 2, left, mid, qleft, qright, val);
        return leftmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    return min(leftmost_lower(root * 2, left, mid, qleft, qright, val),
               leftmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val));
}


int rightmost_higher(int root, int left, int right,
                     int qleft, int qright, int val)
{

    if (left > qright || right < qleft ||
            tree[root].max_num <= val)
        return 0;

    if (left == right)
        return left;
    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2 + 1].max_num > val)
            return rightmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return rightmost_higher(root * 2, left, mid, qleft, qright, val);
    }

    return max(rightmost_higher(root * 2, left, mid, qleft, qright, val),
               rightmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int leftmost_higher(int root, int left, int right,
                    int qleft, int qright, int val)
{
    ///cout << "here " << left << " " << right << " " << val << " " << tree[root].max_num << " " << qleft << " " << qright <<  endl;
    if (left > qright || right < qleft ||
            tree[root].max_num <= val)
        return n + 1;

    if (left == right)
        return left;
    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        ///cout << tree[root * 2].max_num << endl;
        if (tree[root * 2].max_num > val)
            return leftmost_higher(root * 2, left, mid, qleft, qright, val);
        return leftmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    return min(leftmost_higher(root * 2, left, mid, qleft, qright, val),
               leftmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int answer_line_query(query cur)
{
    int lbs = rightmost_lower(1, 1, n, 1, chain_idx[cur.s], cur.l);
    int rbs = leftmost_lower(1, 1, n, chain_idx[cur.s], n, cur.l);

    int lbe = rightmost_higher(1, 1, n, 1, chain_idx[cur.e], cur.r);
    int rbe = leftmost_higher(1, 1, n, chain_idx[cur.e], n, cur.r);

    lbs ++;
    rbs --;
    lbe ++;
    rbe --;
    ///cout << lbs << " : " << rbs << " " << lbe << " " << rbe <<endl;
    if (lbs > lbe)
    {
        swap(lbs, lbe);
        swap(rbs, rbe);
    }
    if (rbs >= lbe)
        return 1;
    return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R)
{
    n = N;
    q = L.size();
    m = X.size();
    for (int i = 0; i < q; i ++)
    {
        ask[i] = query(L[i], R[i], S[i], E[i]);
    }
    for (int i = 0; i < m; i ++)
    {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    if (n <= 3000 && m <= 6000 && q <= 3000)
    {

        vector < int > ans(q, 0);
        for (int i = 0; i < q; i ++)
        {
            ans[i] = solve_query(ask[i]);
        }
        return ans;
    }
    else
    {
        int beg = 1;
        while(graph[beg].size() == 2)
            beg ++;
        make_chain(beg, -1);
        build_tree(1, 1, n);
        vector < int > ans(q);
        /**for (int i = 1; i <= n; i ++)
        {
            cout << chain[i] << " ";
        }
        cout << endl;*/
        for (int i = 0; i < q; i ++)
        {
            ans[i] = answer_line_query(ask[i]);
        }
        return ans;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28496 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 16 ms 28412 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 19 ms 28500 KB Output is correct
8 Correct 15 ms 28504 KB Output is correct
9 Correct 15 ms 28504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28496 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 16 ms 28412 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 19 ms 28500 KB Output is correct
8 Correct 15 ms 28504 KB Output is correct
9 Correct 15 ms 28504 KB Output is correct
10 Correct 247 ms 28764 KB Output is correct
11 Correct 151 ms 28760 KB Output is correct
12 Correct 33 ms 28764 KB Output is correct
13 Correct 267 ms 28756 KB Output is correct
14 Correct 181 ms 28756 KB Output is correct
15 Correct 214 ms 28876 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 56040 KB Output is correct
2 Correct 350 ms 64332 KB Output is correct
3 Correct 305 ms 64336 KB Output is correct
4 Correct 364 ms 64380 KB Output is correct
5 Correct 403 ms 64372 KB Output is correct
6 Correct 568 ms 64352 KB Output is correct
7 Correct 451 ms 64304 KB Output is correct
8 Correct 337 ms 64340 KB Output is correct
9 Correct 308 ms 64268 KB Output is correct
10 Correct 336 ms 64296 KB Output is correct
11 Correct 414 ms 64328 KB Output is correct
12 Correct 451 ms 64352 KB Output is correct
13 Correct 369 ms 64332 KB Output is correct
14 Correct 376 ms 64328 KB Output is correct
15 Correct 359 ms 64332 KB Output is correct
16 Correct 360 ms 64332 KB Output is correct
17 Correct 453 ms 64392 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28496 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 16 ms 28412 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 15 ms 28508 KB Output is correct
7 Correct 19 ms 28500 KB Output is correct
8 Correct 15 ms 28504 KB Output is correct
9 Correct 15 ms 28504 KB Output is correct
10 Correct 247 ms 28764 KB Output is correct
11 Correct 151 ms 28760 KB Output is correct
12 Correct 33 ms 28764 KB Output is correct
13 Correct 267 ms 28756 KB Output is correct
14 Correct 181 ms 28756 KB Output is correct
15 Correct 214 ms 28876 KB Output is correct
16 Correct 800 ms 56040 KB Output is correct
17 Correct 350 ms 64332 KB Output is correct
18 Correct 305 ms 64336 KB Output is correct
19 Correct 364 ms 64380 KB Output is correct
20 Correct 403 ms 64372 KB Output is correct
21 Correct 568 ms 64352 KB Output is correct
22 Correct 451 ms 64304 KB Output is correct
23 Correct 337 ms 64340 KB Output is correct
24 Correct 308 ms 64268 KB Output is correct
25 Correct 336 ms 64296 KB Output is correct
26 Correct 414 ms 64328 KB Output is correct
27 Correct 451 ms 64352 KB Output is correct
28 Correct 369 ms 64332 KB Output is correct
29 Correct 376 ms 64328 KB Output is correct
30 Correct 359 ms 64332 KB Output is correct
31 Correct 360 ms 64332 KB Output is correct
32 Correct 453 ms 64392 KB Output is correct
33 Incorrect 707 ms 55176 KB Output isn't correct
34 Halted 0 ms 0 KB -