Submission #1015166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015166		deera	Werewolf (IOI18_werewolf)	C++14	15 / 100	266 ms	61312 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 1, LG = 19; //(int)log2(MAX_N);
int mx[LG][MAX_N], mn[LG][MAX_N];

int getMN(int l, int r)
{
    int i = 0, p2 = 1;
    while (p2 <= r - l + 1)
        ++i, p2 <<= 1;
    --i, p2 >>= 1;
    return min(mn[i][l], mn[i][r - p2 + 1]);
}

int getMX(int l, int r)
{
    int i = 0, p2 = 1;
    while (p2 <= r - l + 1)
        ++i, p2 <<= 1;
    --i, p2 >>= 1;
    return max(mx[i][l], mx[i][r - p2 + 1]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    int M = X.size(), Q = S.size();
    vector<int> A(Q);

    if (N <= 3000 && M <= 6000 && Q <= 3000)
    {
        vector<vector<int>> g(N);
        for (int i = 0; i < M; ++i)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }

        for (int qq = 0; qq < Q; ++qq)
        {
            int s = S[qq], e = E[qq], l = L[qq], r = R[qq];

            vector<bool> H(N);
            queue<int> q;
            q.push(s), H[s] = true;
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (int y : g[x])
                {
                    if (!H[y] && y >= l)
                        q.push(y), H[y] = true;
                }
            }

            vector<bool> W(N);
            q.push(e), W[e] = true;
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (int y : g[x])
                {
                    if (!W[y] && y <= r)
                        q.push(y), W[y] = true;
                }
            }

            for (int i = 0; i < N; ++i)
            {
                if (H[i] && W[i] && l <= i && i <= r)
                    A[qq] = 1;
            }
        }
    }
    else
    {
        vector<vector<int>> g(N);
        for (int i = 0; i < M; ++i)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }

        int endPoint = 0;
        for (int i = 0; i < N; ++i)
        {
            if (g[i].size() == 1)
            {
                endPoint = i;
                break;
            }
        }

        
        vector<int> id(N);
        id[0] = endPoint;
        for (int i = 1, cur = g[id[0]][0]; i < N; ++i)
        {
            id[i] = cur;
            cur = g[cur][0] + g[cur][1] - id[i - 1];
        }

        vector<int> linePos(N);
        for (int i = 0; i < N; ++i)
            linePos[id[i]] = i;

        for (int i = 0; i < N; ++i)
            mx[0][i] = mn[0][i] = id[i];
        for (int i = 1, p2 = 1; i < LG; ++i, p2 <<= 1)
        {
            for (int j = 0; j < N; ++j)
            {
                mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + p2]);
                mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + p2]);
            }
        }

        for (int qq = 0; qq < Q; ++qq)
        {
            int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
            s = linePos[s], e = linePos[e];

            if (s < e)
            {
                int l = s - 1, r = e; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMX(mid, e) > r)
                        l = mid;
                    else
                        r = mid;
                }
                int lastH = l;

                l = s, r = e + 1; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMN(s, mid) < l)
                        r = mid;
                    else
                        l = mid;
                }
                int firstW = r;

                if (lastH + 1 < firstW)
                    A[qq] = 1;
            }
            else
            {
                int l = e - 1, r = s; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMN(mid, s) < l)
                        l = mid;
                    else
                        r = mid;
                }
                int lastW = l;

                l = e, r = s + 1;
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMX(e, mid) > r)
                        r = mid;
                    else
                        l = mid;
                }
                int firstH = r;

                if (lastW + 1 < firstH)
                    A[qq] = 1;
            }
        }
    }

    return A;
}

Compilation message (stderr)

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:124:39: warning: unused variable 'l' [-Wunused-variable]
  124 |             int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      |                                       ^
werewolf.cpp:124:50: warning: unused variable 'r' [-Wunused-variable]
  124 |             int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      |                                                  ^

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