Submission #292702

#	Time	Username	Problem	Language	Result	Execution time	Memory
292702		SamAnd	Werewolf (IOI18_werewolf)	C++17	100 / 100	1971 ms	160360 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 400005;

int n, m, qq;
vector<int> g[N];

void dfs00(int x, int ul, int ur, vector<bool>& c)
{
    if (!(ul <= x && x <= ur))
        return;
    if (c[x])
        return;
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs00(h, ul, ur, c);
    }
}

vector<int> solv0(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)
{
    vector<int> ans;
    for (int i = 0; i < qq; ++i)
    {
        vector<bool> cs, ce;
        cs.assign(n, false);
        ce.assign(n, false);
        dfs00(S[i], L[i], n - 1, cs);
        dfs00(E[i], 0, R[i], ce);
        for (int x = 0; x < n; ++x)
        {
            if (cs[x] && ce[x])
            {
                ans.push_back(1);
                break;
            }
        }
        if (sz(ans) != (i + 1))
            ans.push_back(0);
    }
    return ans;
}

int p0[N];
int fi(int x)
{
    if (x == p0[x])
        return x;
    return p0[x] = fi(p0[x]);
}

vector<vector<int> > g1, g2;

int tin1[N], tout1[N], ti1;
int tin2[N], tout2[N], ti2;
const int k = 20;
int p1[N][k], p2[N][k];

void dfs0(int x, int p0, vector<vector<int> >& g, int tin[], int tout[], int& ti, int p[][k])
{
    tin[x] = ++ti;
    p[x][0] = p0;
    for (int i = 1; i < k; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs0(h, x, g, tin, tout, ti, p);
    }
    tout[x] = ti;
}

int go1(int x, int l)
{
    for (int i = k - 1; i >= 0; --i)
    {
        if (p1[x][i] >= l)
            x = p1[x][i];
    }
    return x;
}

int go2(int x, int r)
{
    for (int i = k - 1; i >= 0; --i)
    {
        if (p2[x][i] <= r)
            x = p2[x][i];
    }
    return x;
}

int rtin2[N], rtin1[N];

int z;
int t[N * k];
int ul[N * k], ur[N * k];
int ubd(int tl, int tr, int x, int pos)
{
    int ypos = ++z;
    ul[ypos] = ul[pos];
    ur[ypos] = ur[pos];
    t[ypos] = t[pos];
    if (tl == tr)
    {
        t[ypos]++;
        return ypos;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ul[ypos] = ubd(tl, m, x, ul[pos]);
    else
        ur[ypos] = ubd(m + 1, tr, x, ur[pos]);
    t[ypos] = t[ul[ypos]] + t[ur[ypos]];
    return ypos;
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return (qry(tl, m, l, min(m, r), ul[pos]) +
            qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}

int root[N];

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 = sz(X);
    qq = sz(S);
    for (int i = 0; i < m; ++i)
    {
        int x = X[i];
        int y = Y[i];
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<int> ans;

    g1.resize(n);
    g2.resize(n);

    for (int x = 0; x < n; ++x)
        p0[x] = x;
    vector<pair<int, int> > v;
    for (int i = 0; i < m; ++i)
    {
        if (X[i] > Y[i])
            swap(X[i], Y[i]);
        v.push_back(m_p(X[i], Y[i]));
    }
    sort(all(v));
    reverse(all(v));
    for (int i = 0; i < m; ++i)
    {
        int x = v[i].fi;
        int y = v[i].se;
        x = fi(x);
        y = fi(y);
        if (x == y)
            continue;
        g1[x].push_back(y);
        p0[y] = x;
    }

    for (int x = 0; x < n; ++x)
        p0[x] = x;
    v.clear();
    for (int i = 0; i < m; ++i)
    {
        swap(X[i], Y[i]);
        v.push_back(m_p(X[i], Y[i]));
    }
    sort(all(v));
    for (int i = 0; i < m; ++i)
    {
        int x = v[i].fi;
        int y = v[i].se;
        x = fi(x);
        y = fi(y);
        if (x == y)
            continue;
        g2[x].push_back(y);
        p0[y] = x;
    }

    dfs0(0, 0, g1, tin1, tout1, ti1, p1);
    dfs0(n - 1, n - 1, g2, tin2, tout2, ti2, p2);

    for (int x = 0; x < n; ++x)
    {
        rtin2[tin2[x]] = x;
        rtin1[tin1[x]] = x;
    }

    for (int i = 1; i <= n; ++i)
        root[i] = ubd(1, n, tin2[rtin1[i]], root[i - 1]);

    for (int ii = 0; ii < qq; ++ii)
    {
        int x = S[ii];
        int y = E[ii];
        int l = L[ii];
        int r = R[ii];
        x = go1(x, l);
        y = go2(y, r);
        int s = qry(1, n, tin2[y], tout2[y], root[tout1[x]])
            - qry(1, n, tin2[y], tout2[y], root[tin1[x] - 1]);
        if (s)
            ans.push_back(1);
        else
            ans.push_back(0);
    }
    //if (ans != solv0(N_, X, Y, S, E, L, R))
    //    printf("WA\n");
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs00(int, int, int, std::vector<bool>&)':
werewolf.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs0(int, int, std::vector<std::vector<int> >&, int*, int*, int&, int (*)[20])':
werewolf.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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