oj.uz

답안 #1015166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015166 2024-07-06T06:56:36 Z deera 늑대인간 (IOI18_werewolf) C++14
15 / 100
 266 ms 61312 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 1, LG = 19; //(int)log2(MAX_N);
int mx[LG][MAX_N], mn[LG][MAX_N];

int getMN(int l, int r)
{
    int i = 0, p2 = 1;
    while (p2 <= r - l + 1)
        ++i, p2 <<= 1;
    --i, p2 >>= 1;
    return min(mn[i][l], mn[i][r - p2 + 1]);
}

int getMX(int l, int r)
{
    int i = 0, p2 = 1;
    while (p2 <= r - l + 1)
        ++i, p2 <<= 1;
    --i, p2 >>= 1;
    return max(mx[i][l], mx[i][r - p2 + 1]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    int M = X.size(), Q = S.size();
    vector<int> A(Q);

    if (N <= 3000 && M <= 6000 && Q <= 3000)
    {
        vector<vector<int>> g(N);
        for (int i = 0; i < M; ++i)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }

        for (int qq = 0; qq < Q; ++qq)
        {
            int s = S[qq], e = E[qq], l = L[qq], r = R[qq];

            vector<bool> H(N);
            queue<int> q;
            q.push(s), H[s] = true;
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (int y : g[x])
                {
                    if (!H[y] && y >= l)
                        q.push(y), H[y] = true;
                }
            }

            vector<bool> W(N);
            q.push(e), W[e] = true;
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (int y : g[x])
                {
                    if (!W[y] && y <= r)
                        q.push(y), W[y] = true;
                }
            }

            for (int i = 0; i < N; ++i)
            {
                if (H[i] && W[i] && l <= i && i <= r)
                    A[qq] = 1;
            }
        }
    }
    else
    {
        vector<vector<int>> g(N);
        for (int i = 0; i < M; ++i)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }

        int endPoint = 0;
        for (int i = 0; i < N; ++i)
        {
            if (g[i].size() == 1)
            {
                endPoint = i;
                break;
            }
        }

        
        vector<int> id(N);
        id[0] = endPoint;
        for (int i = 1, cur = g[id[0]][0]; i < N; ++i)
        {
            id[i] = cur;
            cur = g[cur][0] + g[cur][1] - id[i - 1];
        }

        vector<int> linePos(N);
        for (int i = 0; i < N; ++i)
            linePos[id[i]] = i;

        for (int i = 0; i < N; ++i)
            mx[0][i] = mn[0][i] = id[i];
        for (int i = 1, p2 = 1; i < LG; ++i, p2 <<= 1)
        {
            for (int j = 0; j < N; ++j)
            {
                mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + p2]);
                mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + p2]);
            }
        }

        for (int qq = 0; qq < Q; ++qq)
        {
            int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
            s = linePos[s], e = linePos[e];

            if (s < e)
            {
                int l = s - 1, r = e; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMX(mid, e) > r)
                        l = mid;
                    else
                        r = mid;
                }
                int lastH = l;

                l = s, r = e + 1; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMN(s, mid) < l)
                        r = mid;
                    else
                        l = mid;
                }
                int firstW = r;

                if (lastH + 1 < firstW)
                    A[qq] = 1;
            }
            else
            {
                int l = e - 1, r = s; 
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMN(mid, s) < l)
                        l = mid;
                    else
                        r = mid;
                }
                int lastW = l;

                l = e, r = s + 1;
                while (l + 1 < r)
                {
                    int mid = (l + r) / 2;
                    if (getMX(e, mid) > r)
                        r = mid;
                    else
                        l = mid;
                }
                int firstH = r;

                if (lastW + 1 < firstH)
                    A[qq] = 1;
            }
        }
    }

    return A;
}

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:124:39: warning: unused variable 'l' [-Wunused-variable]
  124 |             int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      |                                       ^
werewolf.cpp:124:50: warning: unused variable 'r' [-Wunused-variable]
  124 |             int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      |                                                  ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 187 ms 860 KB Output is correct
11 Correct 102 ms 856 KB Output is correct
12 Correct 17 ms 860 KB Output is correct
13 Correct 210 ms 872 KB Output is correct
14 Correct 120 ms 860 KB Output is correct
15 Correct 173 ms 860 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 187 ms 860 KB Output is correct
11 Correct 102 ms 856 KB Output is correct
12 Correct 17 ms 860 KB Output is correct
13 Correct 210 ms 872 KB Output is correct
14 Correct 120 ms 860 KB Output is correct
15 Correct 173 ms 860 KB Output is correct
16 Incorrect 266 ms 61312 KB Output isn't correct
17 Halted 0 ms 0 KB -