Submission #254152

#	Time	Username	Problem	Language	Result	Execution time	Memory
254152		davitmarg	Werewolf (IOI18_werewolf)	C++17	15 / 100	1117 ms	325612 KiB

werewolf

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)


#ifndef death
#include "werewolf.h"
#endif

using namespace std;

const int N = 200005;

int parent[N], sz[N], P[N], id[N + N];
int timer, tin[N + N], tout[N + N],up[N+N][30], mx[N+N][30];
int m,k;
vector<int> G[N + N];

void init(int n,int x=0)
{
    m = n;
    timer = 0;
    for (int i = 1; i <= n; i++)
    {
        G[i].clear();
        id[i] = x;
        G[i+n].clear();
        tin[i] = tin[i + n] = 0;
        P[i] = i;
        parent[i] = i;
        sz[i] = 1;
    }
}

int getPar(int v)
{
    if (parent[v] == v)
        return v;
    return parent[v] = getPar(parent[v]);
}

void dsu(int a, int b,int val)
{
    a = getPar(a);
    b = getPar(b);
    if (a == b)
        return;
    if (sz[a] < sz[b])
        swap(a, b);
    m++;
    G[m].push_back(P[a]);
    G[m].push_back(P[b]);
    parent[b] = a;
    sz[a] += sz[b];
    P[a] = m;
    id[m] = val;
}

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    mx[v][0] = max(id[p], id[v]);

    for (int i = 1; i <= k; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
    }

    for (int i = 0; i < G[v].size(); i++)
    {
        int to = G[v][i];
        //cout << v << " : " << to << endl;
        dfs(to, v);
    }
    tout[v] = timer;
}

int n,x[N],y[N],q;
vector<int> g[N];
pair<int, int> s[N],e[N];

vector<int> t[4 * N];

void add(int v, int l, int r,int pos,int val)
{
    t[v].push_back(val);
    if (l == r)
        return;
    int m = (l + r) / 2;
    if (pos <= m)
        add(v * 2, l, m, pos, val);
    else
        add(v * 2 + 1, m + 1, r, pos, val);
}

void build(int v, int l, int r)
{
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    sort(all(t[v]));
}

bool get(int v, int l, int r, int i, int j, int L, int R)
{
    if (i > j)
        return 0;
    if (l == i && r == j)
    {
        if (t[v].empty())
            return 0;
        if (t[v][0] > R || t[v].back() < L)
            return 0;
        return (*lower_bound(all(t[v]), L) <= R);
    }
    int m = (l + r) / 2;
    return (
        get(v * 2, l, m, i, min(m, j), L, R) |
        get(v * 2 + 1, m + 1, r, max(m + 1, i), j, L, R));
}

vector<int> ans;

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 = S.size();
    for (int i = 0; i < X.size();i++)
    {
        g[X[i] + 1].push_back(Y[i] + 1);
        g[Y[i] + 1].push_back(X[i] + 1);
    }

    //E
    init(n);
    for (int v = 1; v <= n; v++)
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (to > v)
                continue;
            dsu(v, to, v);
        }
    k = 0;
    while ((1 << k) <= m)
        k++;

    for (int i = 1; i <= n; i++)
    {
        int v = P[getPar(i)];
        if (!tin[v])
            dfs(v, v);
    }

    for (int v = 1; v <= n; v++)
        x[v] = tin[v];
    
    for (int i = 0; i < E.size(); i++)
    {
        E[i]++;
        R[i]++;
        int v = E[i];
        for (int j = k; j >= 0; j--)
            if (mx[v][j] <= R[i])
                v = up[v][j];
        e[i + 1] = MP(tin[v], tout[v]);
    }

    //S

    init(n, -n - 1);
    for (int v = n; v >= 1; v--)
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (to < v)
                continue;
            dsu(v, to, -v);
        }

    k = 0;
    while ((1 << k) <= m)
        k++;

    for (int i = 1; i <= n; i++)
    {
        int v = P[getPar(i)];
        if (!tin[v])
            dfs(v, v);
    }

    for (int v = 1; v <= n; v++)
        y[v] = tin[v];

    for (int i = 0; i < S.size(); i++)
    {
        S[i]++;
        L[i]++;
        int v = S[i];
        for (int j = k; j >= 0; j--)
            if (mx[v][j] <= -L[i])
                v = up[v][j];
        s[i + 1] = MP(tin[v], tout[v]);
    }

    for (int i = 1; i <= n; i++)
        add(1, 1, n + n,y[i], x[i]);

    build(1, 1, n + n);

    for (int i = 1; i <= q; i++)
        ans.push_back(get(1, 1, n + n, s[i].first, s[i].second, e[i].first, e[i].second));
    return ans;
}

#ifdef death
int main()
{
    fastIO;
    int n, m, q;
    vector<int> X, Y, L, R, S, E;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        X.PB(a);
        Y.PB(b);
    }

    for (int i = 0; i < q; i++)
    {
        int a, b,l,r;
        cin >> a >> b >> l >> r;
        S.PB(a);
        E.PB(b);
        L.PB(l);
        R.PB(r);
    }

    vector<int> ANS = check_validity(n, X, Y, S, E, L, R);
    for (int i = 0; i < ANS.size(); i++)
        cout << ANS[i] << endl;
    return 0;
}

#endif

/*




*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < G[v].size(); i++)
                     ~~^~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size();i++)
                     ~~^~~~~~~~~~
werewolf.cpp:167:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~
werewolf.cpp:188:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < E.size(); i++)
                     ~~^~~~~~~~~~
werewolf.cpp:203:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~
werewolf.cpp:225:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); i++)
                     ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51