oj.uz

Submission #401149

# Submission time Handle Problem Language Result Execution time Memory
401149 2021-05-09T13:25:55 Z idk321 Werewolf (IOI18_werewolf) C++11
0 / 100
 546 ms 91336 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int N = 200000;

vector<int> adj[N];
vector<int> s;
vector<int> e;
vector<int> l;
vector<int> r;
vector<int> x;
vector<int> y;
int n;
int q;

vector<int> line;

int bit[N][20][2];
int bit2[N][20][2];

vector<int> vis[2];

void dfs(int node, int q1, int typ)
{
    if (typ == 0 && node < l[q1]) return;
    if (typ == 1 && node > r[q1]) return;
    vis[typ][node] = true;
    for (int next : adj[node])
    {
        if (vis[typ][next]) continue;
        dfs(next, q1, typ);
    }
}

void cons1()
{
    for (int i = 0; i < n; i++)
    {
        bit[i][0][0] = line[i];
        bit[i][0][1] = line[i];
    }

    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)
        {
            bit[i][j][0] = min(bit[i][j - 1][0], bit[i + (1 << (j - 1))][j - 1][0]);
            bit[i][j][1] = max(bit[i][j - 1][1], bit[i + (1 << (j - 1))][j - 1][1]);
        }
    }
}

void cons2()
{
    for (int i = 0; i < n; i++)
    {
        bit2[i][0][0] = line[i];
        bit2[i][0][1] = line[i];
    }

    for (int j = 1; j < 20; j++)
    {
        for (int i = n - 1; i - (1 << j) + 1 >= 0; i--)
        {
            bit2[i][j][0] = min(bit2[i][j - 1][0], bit2[i - (1 << (j - 1))][j - 1][0]);
            bit2[i][j][1] = max(bit2[i][j - 1][1], bit2[i - (1 << (j - 1))][j - 1][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;
    x =X;
    y =Y;
    s =S;
    e =E;
    l = L;
    r =R;

    for (int i = 0; i < x.size(); i++)
    {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

  q = S.size();
  std::vector<int> res(q);
  if (n <= 3000 && q <= 3000)
  {


    for (int q1 = 0; q1 < q; q1++)
    {
        if (s[q1] < l[q1])
        {
            res[q1] = 0;
            continue;
        }
        if (e[q1] > r[q1])
        {
            res[q1] = 0;
            continue;
        }

        vis[0].clear();
        vis[0].resize(n);
        vis[1].clear();
        vis[1].resize(n);
        dfs(s[q1], q1, 0);
        dfs(e[q1], q1, 1);
        for (int i = 0; i < n; i++) if (vis[0][i] && vis[1][i])
        {
            res[q1] = 1;
        }
    }

  }



  vector<int> res2 = res;
  if (true)
  {
    for (int i = 0; i < n; i++)
    {
        if (adj[i].size() == 1)
        {
            line.push_back(i);
            break;
        }
    }

    int prev = -1;
    while (true)
    {
        int cnext = - 1;
        for (int next : adj[line.back()])
        {
            if (next != prev)
            {
                cnext = next;
            }
        }
        prev = line.back();
        if (cnext == -1) break;
        line.push_back(cnext);
    }


    vector<int> isAt(n);
    for (int i = 0; i < n; i++) isAt[line[i]] = i;
    cons1();
    cons2();

    for (int q1 = 0; q1 < q; q1++)
    {


        int a = isAt[s[q1]];
        int b = isAt[e[q1]];

        if (a < b)
        {

            for (int i = 19; i >= 0; i--)
            {
                if (a + ((1 << i)) <= n && bit[a][i][0] >= l[q1])
                {
                    a += (1 << i);
                }
            }

            for (int i = 19; i >= 0; i--)
            {
                if (b - ((1 << i)) >= -1 && bit2[b][i][1] <= r[q1])
                {
                    b -= ((1 << i));
                }
            }


            if (1 + a >= b) res[q1] = 1;
        } else
        {

            swap(a, b);
            //cout << a << " " << b << endl;
            for (int i = 19; i >= 0; i--)
            {
                if (a + ((1 << i)) <= n && bit[a][i][1] <= r[q1])
                {
                    //cout << i << " " << a << " " << bit[a][i][1] << endl;
                    a += (1 << i);
                }
            }

            for (int i = 19; i >= 0; i--)
            {
                if (b - ((1 << i)) >= -1 && bit2[b][i][0] >= l[q1])
                {
                    //cout << i << " " << b << " " << bit2[b][i][0] << endl;
                    b -= ((1 << i));
                }
            }

            //cout << a << " " << b << endl;
            if (1 + a > b) res[q1] = 1;
        }
    }

  }

/*
  for (int i = 0;  i< q; i++)
  {
    if (res[i] != res2[i])
    {
        cout << s[i] << " a " << e[i] << " " << l[i] << " "<< r[i] << " " << res[i] << " " << res2[i]<< " " << i << endl;
    }
  } */
  return res;
}

/*
5 4 1
3 1
1 2
2 0
4 3
1 0 1 0
*/

Compilation message

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:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 546 ms 91336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -