Submission #291687

#	Time	Username	Problem	Language	Result	Execution time	Memory
291687		SamAnd	Werewolf (IOI18_werewolf)	C++17	15 / 100	974 ms	524288 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 dfs(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];
        dfs(h, ul, ur, c);
    }
}

pair<int, int> t[N * 4];

pair<int, int> mer(const pair<int, int>& l, const pair<int, int>& r)
{
    return m_p(min(l.fi, r.fi), max(l.se, r.se));
}

void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[pos] = m_p(y, y);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

pair<int, int> qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return m_p(n, 0);
    if (tl == l && tr == r)
    {
        return t[pos];
    }
    int m = (tl + tr) / 2;
    return mer(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

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;
    if (n <= 3000 && m <= 6000 && qq <= 3000)
    {
        for (int i = 0; i < qq; ++i)
        {
            vector<bool> cs, ce;
            cs.assign(n, false);
            ce.assign(n, false);
            dfs(S[i], L[i], n - 1, cs);
            dfs(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;
    }

    vector<int> v;
    for (int x = 0; x < n; ++x)
    {
        if (sz(g[x]) != 1)
            continue;
        vector<bool> c;
        c.assign(n, false);

        c[x] = true;
        v.push_back(x);
        while (1)
        {
            int nx = x;
            for (int i = 0; i < g[x].size(); ++i)
            {
                int h = g[x][i];
                if (!c[h])
                {
                    x = h;
                    break;
                }
            }
            if (x == nx)
                break;
            x = nx;
            c[x] = true;
            v.push_back(x);
        }
        break;
    }
    vector<int> u(n);
    for (int i = 0; i < n; ++i)
    {
        u[v[i]] = i;
        ubd(0, n - 1, i, v[i], 1);
    }

    for (int i = 0; i < qq; ++i)
    {
        if (u[S[i]] < u[E[i]])
        {
            int l = u[S[i]], r = n - 1;
            int uu;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (qry(0, n - 1, u[S[i]], m, 1).fi >= L[i])
                {
                    uu = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }
            if (qry(0, n - 1, uu, u[E[i]], 1).se <= R[i])
                ans.push_back(1);
            else
                ans.push_back(0);
        }
        else
        {
            int l = u[E[i]], r = n - 1;
            int uu;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (qry(0, n - 1, u[E[i]], m, 1).se <= R[i])
                {
                    uu = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }
            if (qry(0, n - 1, uu, u[S[i]], 1).fi >= L[i])
                ans.push_back(1);
            else
                ans.push_back(0);
        }
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(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 '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:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int i = 0; i < g[x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~
werewolf.cpp:177:45: warning: 'uu' may be used uninitialized in this function [-Wmaybe-uninitialized]
  177 |             if (qry(0, n - 1, uu, u[S[i]], 1).fi >= L[i])
      |                                             ^
werewolf.cpp:157:45: warning: 'uu' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |             if (qry(0, n - 1, uu, u[E[i]], 1).se <= R[i])
      |                                             ^

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