제출 #588549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588549		georgievskiy	늑대인간 (IOI18_werewolf)	C++17	34 / 100	1121 ms	37780 KiB

werewolf

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51