oj.uz

답안 #588549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588549 2022-07-03T13:45:07 Z georgievskiy 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1121 ms 37780 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
//const int N = 100;
const int inf = 2e9;

struct ST_min {
    int t[4 * N];
    void build(int v, int tl, int tr, vector<int>&x) {
        if (tl + 1 == tr) {
            if (tl < x.size())
                t[v] = x[tl];
            else
                t[v] = inf;
            return;
        }
        int m = (tl + tr) / 2;
        build(2 * v + 1, tl, m, x);
        build(2 * v + 2, m, tr, x);
        t[v] = min(t[2 * v + 1], t[2 * v + 2]);
    }
    int get(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return inf;
        if (tl >= l && tr <= r)
            return t[v];
        int m = (tl + tr) / 2;
        int p1 = get(2 * v + 1, tl, m, l, r);
        int p2 = get(2 * v + 2, m, tr, l, r);
        return min(p1, p2);
    }
};

struct ST_max {
    int t[4 * N];
    void build(int v, int tl, int tr, vector<int>&x) {
        if (tl + 1 == tr) {
            if (tl < x.size())
                t[v] = x[tl];
            else
                t[v] = -inf;
            return;
        }
        int m = (tl + tr) / 2;
        build(2 * v + 1, tl, m, x);
        build(2 * v + 2, m, tr, x);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }
    int get(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return -inf;
        if (tl >= l && tr <= r)
            return t[v];
        int m = (tl + tr) / 2;
        int p1 = get(2 * v + 1, tl, m, l, r);
        int p2 = get(2 * v + 2, m, tr, l, r);
        return max(p1, p2);
    }
};

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) {

    int m = X.size(), q = S.size();
    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]);
    vector<int> a(n);
    int s;
    for (int i = 0; i < n; i++)
        if (g[i].size() == 1) {
            s = i;
            a[0] = i, a[1] = g[i].front();
            break;
        }
    for (int i = 2; i < n; i++) {
        int x = g[a[i - 1]].front(), y = g[a[i - 1]].back();
        if (x != a[i - 2])
            a[i] = x;
        else
            a[i] = y;
    }
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[a[i]] = i;

    ST_min mn; ST_max mx;
    mn.build(0, 0, n, a);
    mx.build(0, 0, n, a);

    vector<int> ans(q, 0);

    for (int i = 0; i < q; i++) {
        int s = p[S[i]], e = p[E[i]];
        if (s < e) {
            int l = s, r = n;
            while (r - l > 1) {
                int c = (r + l) / 2;
                if (mn.get(0, 0, n, s, c+1) >= L[i])
                    l = c;
                else
                    r = c;
            }
            if (l >= e) {
                ans[i] = 1;
                continue;
            }
            ans[i] = mx.get(0, 0, n, l, e+1) <= R[i];
        } else {
            int l = e, r = n;
            while (r - l > 1) {
                int c = (r + l) / 2;
                if (mx.get(0, 0, n, e, c+1) <= R[i])
                    l = c;
                else
                    r = c;
            }
            if (l >= s) {
                ans[i] = 1;
                continue;
            }
            ans[i] = mn.get(0, 0, n, l, s+1) >= L[i];
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In member function 'void ST_min::build(int, int, int, std::vector<int>&)':
werewolf.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |             if (tl < x.size())
      |                 ~~~^~~~~~~~~~
werewolf.cpp: In member function 'void ST_max::build(int, int, int, std::vector<int>&)':
werewolf.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if (tl < x.size())
      |                 ~~~^~~~~~~~~~
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:71:9: warning: variable 's' set but not used [-Wunused-but-set-variable]
   71 |     int s;
      |         ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1121 ms 29292 KB Output is correct
2 Correct 990 ms 37688 KB Output is correct
3 Correct 968 ms 37692 KB Output is correct
4 Correct 1093 ms 37692 KB Output is correct
5 Correct 1045 ms 37696 KB Output is correct
6 Correct 1063 ms 37688 KB Output is correct
7 Correct 1059 ms 37692 KB Output is correct
8 Correct 976 ms 37692 KB Output is correct
9 Correct 747 ms 37708 KB Output is correct
10 Correct 533 ms 37672 KB Output is correct
11 Correct 687 ms 37708 KB Output is correct
12 Correct 767 ms 37756 KB Output is correct
13 Correct 1039 ms 37692 KB Output is correct
14 Correct 975 ms 37780 KB Output is correct
15 Correct 979 ms 37740 KB Output is correct
16 Correct 992 ms 37700 KB Output is correct
17 Correct 1033 ms 37692 KB Output is correct

Subtask #4
0 / 51.0

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