Submission #738164

#	Time	Username	Problem	Language	Result	Execution time	Memory
738164		danikoynov	Werewolf (IOI18_werewolf)	C++14	49 / 100	800 ms	64392 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51