Submission #292691

#	Time	Username	Problem	Language	Result	Execution time	Memory
292691		SamAnd	Werewolf (IOI18_werewolf)	C++17	15 / 100	4026 ms	80096 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;
}

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 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);
        for (int u = 0; u < n; ++u)
        {
            if (tin1[x] <= tin1[u] && tin1[u] <= tout1[x])
            {
                if (tin2[y] <= tin2[u] && tin2[u] <= tout2[y])
                {
                    ans.push_back(1);
                    break;
                }
            }
        }
        if (sz(ans) == ii)
            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: 0 / 34
• Subtask 4: 0 / 51