oj.uz

답안 #401151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401151 2021-05-09T13:28:14 Z idk321 늑대인간 (IOI18_werewolf) C++11
15 / 100
 534 ms 90468 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 (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 190
3 1
1 2
2 0
4 3
0 1 0 1
0 1 0 2
0 1 0 3
0 1 0 4
0 2 0 2
0 2 0 3
0 2 0 4
0 3 0 3
0 3 0 4
0 4 0 4
1 0 0 0
1 0 0 1
1 0 0 2
1 0 0 3
1 0 0 4
1 0 1 0
1 0 1 1
1 0 1 2
1 0 1 3
1 0 1 4
1 2 0 2
1 2 0 3
1 2 0 4
1 2 1 2
1 2 1 3
1 2 1 4
1 3 0 3
1 3 0 4
1 3 1 3
1 3 1 4
1 4 0 4
1 4 1 4
2 0 0 0
2 0 0 1
2 0 0 2
2 0 0 3
2 0 0 4
2 0 1 0
2 0 1 1
2 0 1 2
2 0 1 3
2 0 1 4
2 0 2 0
2 0 2 1
2 0 2 2
2 0 2 3
2 0 2 4
2 1 0 1
2 1 0 2
2 1 0 3
2 1 0 4
2 1 1 1
2 1 1 2
2 1 1 3
2 1 1 4
2 1 2 1
2 1 2 2
2 1 2 3
2 1 2 4
2 3 0 3
2 3 0 4
2 3 1 3
2 3 1 4
2 3 2 3
2 3 2 4
2 4 0 4
2 4 1 4
2 4 2 4
3 0 0 0
3 0 0 1
3 0 0 2
3 0 0 3
3 0 0 4
3 0 1 0
3 0 1 1
3 0 1 2
3 0 1 3
3 0 1 4
3 0 2 0
3 0 2 1
3 0 2 2
3 0 2 3
3 0 2 4
3 0 3 0
3 0 3 1
3 0 3 2
3 0 3 3
3 0 3 4
3 1 0 1
3 1 0 2
3 1 0 3
3 1 0 4
3 1 1 1
3 1 1 2
3 1 1 3
3 1 1 4
3 1 2 1
3 1 2 2
3 1 2 3
3 1 2 4
3 1 3 1
3 1 3 2
3 1 3 3
3 1 3 4
3 2 0 2
3 2 0 3
3 2 0 4
3 2 1 2
3 2 1 3
3 2 1 4
3 2 2 2
3 2 2 3
3 2 2 4
3 2 3 2
3 2 3 3
3 2 3 4
3 4 0 4
3 4 1 4
3 4 2 4
3 4 3 4
4 0 0 0
4 0 0 1
4 0 0 2
4 0 0 3
4 0 0 4
4 0 1 0
4 0 1 1
4 0 1 2
4 0 1 3
4 0 1 4
4 0 2 0
4 0 2 1
4 0 2 2
4 0 2 3
4 0 2 4
4 0 3 0
4 0 3 1
4 0 3 2
4 0 3 3
4 0 3 4
4 0 4 0
4 0 4 1
4 0 4 2
4 0 4 3
4 0 4 4
4 1 0 1
4 1 0 2
4 1 0 3
4 1 0 4
4 1 1 1
4 1 1 2
4 1 1 3
4 1 1 4
4 1 2 1
4 1 2 2
4 1 2 3
4 1 2 4
4 1 3 1
4 1 3 2
4 1 3 3
4 1 3 4
4 1 4 1
4 1 4 2
4 1 4 3
4 1 4 4
4 2 0 2
4 2 0 3
4 2 0 4
4 2 1 2
4 2 1 3
4 2 1 4
4 2 2 2
4 2 2 3
4 2 2 4
4 2 3 2
4 2 3 3
4 2 3 4
4 2 4 2
4 2 4 3
4 2 4 4
4 3 0 3
4 3 0 4
4 3 1 3
4 3 1 4
4 3 2 3
4 3 2 4
4 3 3 3
4 3 3 4
4 3 4 3
4 3 4 4
*/

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 5064 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 5 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5064 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 5 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 309 ms 5452 KB Output is correct
11 Correct 182 ms 5324 KB Output is correct
12 Correct 34 ms 5464 KB Output is correct
13 Correct 338 ms 5356 KB Output is correct
14 Correct 220 ms 5332 KB Output is correct
15 Correct 268 ms 5480 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5064 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 5 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 309 ms 5452 KB Output is correct
11 Correct 182 ms 5324 KB Output is correct
12 Correct 34 ms 5464 KB Output is correct
13 Correct 338 ms 5356 KB Output is correct
14 Correct 220 ms 5332 KB Output is correct
15 Correct 268 ms 5480 KB Output is correct
16 Incorrect 534 ms 90468 KB Output isn't correct
17 Halted 0 ms 0 KB -