oj.uz

Submission #401135

# Submission time Handle Problem Language Result Execution time Memory
401135 2021-05-09T12:35:34 Z idk321 Werewolf (IOI18_werewolf) C++11
15 / 100
 539 ms 90452 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++)
    {
        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++)
    {
        if (s[q1] < l[q1])
        {
            res[q1] = 0;
            continue;
        }
        if (e[q1] > r[q1])
        {
            res[q1] = 0;
            continue;
        }

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

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

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


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

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

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

  return res;
}

/*
10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
1 7 1 8

*/

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 4980 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 4980 KB Output is correct
10 Correct 315 ms 5324 KB Output is correct
11 Correct 179 ms 5328 KB Output is correct
12 Correct 34 ms 5452 KB Output is correct
13 Correct 338 ms 5400 KB Output is correct
14 Correct 217 ms 5324 KB Output is correct
15 Correct 266 ms 5488 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 539 ms 90452 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 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 4980 KB Output is correct
10 Correct 315 ms 5324 KB Output is correct
11 Correct 179 ms 5328 KB Output is correct
12 Correct 34 ms 5452 KB Output is correct
13 Correct 338 ms 5400 KB Output is correct
14 Correct 217 ms 5324 KB Output is correct
15 Correct 266 ms 5488 KB Output is correct
16 Incorrect 539 ms 90452 KB Output isn't correct
17 Halted 0 ms 0 KB -