oj.uz

Submission #401152

# Submission time Handle Problem Language Result Execution time Memory
401152 2021-05-09T13:31:37 Z idk321 Werewolf (IOI18_werewolf) C++11
49 / 100
 713 ms 96452 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;
        }
    }

  }



  else
  {
    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 ( a > b + 1) res[q1] = 1;
        } else
        {

            swap(a, b);

            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));
                }
            }


            if (a > b + 1) 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 310 ms 5360 KB Output is correct
11 Correct 184 ms 5324 KB Output is correct
12 Correct 34 ms 5452 KB Output is correct
13 Correct 341 ms 5368 KB Output is correct
14 Correct 224 ms 5444 KB Output is correct
15 Correct 265 ms 5496 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 90496 KB Output is correct
2 Correct 713 ms 96376 KB Output is correct
3 Correct 699 ms 96276 KB Output is correct
4 Correct 682 ms 96340 KB Output is correct
5 Correct 688 ms 96184 KB Output is correct
6 Correct 617 ms 96452 KB Output is correct
7 Correct 625 ms 96184 KB Output is correct
8 Correct 606 ms 96280 KB Output is correct
9 Correct 489 ms 96184 KB Output is correct
10 Correct 478 ms 96184 KB Output is correct
11 Correct 494 ms 96184 KB Output is correct
12 Correct 453 ms 96180 KB Output is correct
13 Correct 684 ms 96304 KB Output is correct
14 Correct 684 ms 96184 KB Output is correct
15 Correct 676 ms 96336 KB Output is correct
16 Correct 681 ms 96412 KB Output is correct
17 Correct 602 ms 96280 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 310 ms 5360 KB Output is correct
11 Correct 184 ms 5324 KB Output is correct
12 Correct 34 ms 5452 KB Output is correct
13 Correct 341 ms 5368 KB Output is correct
14 Correct 224 ms 5444 KB Output is correct
15 Correct 265 ms 5496 KB Output is correct
16 Correct 545 ms 90496 KB Output is correct
17 Correct 713 ms 96376 KB Output is correct
18 Correct 699 ms 96276 KB Output is correct
19 Correct 682 ms 96340 KB Output is correct
20 Correct 688 ms 96184 KB Output is correct
21 Correct 617 ms 96452 KB Output is correct
22 Correct 625 ms 96184 KB Output is correct
23 Correct 606 ms 96280 KB Output is correct
24 Correct 489 ms 96184 KB Output is correct
25 Correct 478 ms 96184 KB Output is correct
26 Correct 494 ms 96184 KB Output is correct
27 Correct 453 ms 96180 KB Output is correct
28 Correct 684 ms 96304 KB Output is correct
29 Correct 684 ms 96184 KB Output is correct
30 Correct 676 ms 96336 KB Output is correct
31 Correct 681 ms 96412 KB Output is correct
32 Correct 602 ms 96280 KB Output is correct
33 Runtime error 251 ms 60764 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -