oj.uz

답안 #401140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401140 2021-05-09T12:55:16 Z idk321 늑대인간 (IOI18_werewolf) C++11
15 / 100
 543 ms 90464 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++)
    {
        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)) < n && bit[a][i][0] >= l[q1])
                {
                    a += (1 << i);
                }
            }

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


            if (a >= b) 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])
                {
                    a += (1 << i);
                }
            }

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

            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

2

*/

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

# 결과 실행 시간 메모리 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 4888 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

# 결과 실행 시간 메모리 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 4888 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 350 ms 5364 KB Output is correct
11 Correct 180 ms 5324 KB Output is correct
12 Correct 34 ms 5464 KB Output is correct
13 Correct 345 ms 5360 KB Output is correct
14 Correct 224 ms 5324 KB Output is correct
15 Correct 274 ms 5492 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 543 ms 90464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 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 4888 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 350 ms 5364 KB Output is correct
11 Correct 180 ms 5324 KB Output is correct
12 Correct 34 ms 5464 KB Output is correct
13 Correct 345 ms 5360 KB Output is correct
14 Correct 224 ms 5324 KB Output is correct
15 Correct 274 ms 5492 KB Output is correct
16 Incorrect 543 ms 90464 KB Output isn't correct
17 Halted 0 ms 0 KB -