제출 #1018317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018317		vjudge1	Werewolf (IOI18_werewolf)	C++17	34 / 100	1425 ms	52156 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2E5+16;
const ii IDEM = { MAXN, -MAXN };
vll adj[MAXN];
ll vis[MAXN+MAXN];
ll timer = 1;

ii operator+ (ii a, ii b) {
    return {
        min(a.first, b.first),
        max(a.second, b.second)
    };
}

struct SegTree {
    vii tree;
    ll n;

    SegTree (ll n): tree(2*n, IDEM), n(n) {}

    void update (ll id, ll val) {
        for (tree[id += n] = { val, val }; id > 1; id >>= 1)
            tree[id>>1] = tree[id] + tree[id^1];
    }

    ii query (ll ql, ll qr) {
        ii ans = IDEM;
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) ans = ans + tree[ql++];
            if (qr&1) ans = ans + tree[--qr];
        }
        return ans;
    }
};

vi check_validity (int n, vi us, vi vs, vi s, vi e, vi vl, vi vr) {
    ll Q = s.size();
    for (ll i = 0; i < us.size(); i++) {
        adj[us[i]].push_back(vs[i]);
        adj[vs[i]].push_back(us[i]);
    }
    vll ve;
    function <void(ll, ll)> dfs = [&](ll u, ll par) {
        ve.push_back(u);
        for (ll v : adj[u]) {
            if (v == par) continue;
            dfs(v, u);
        }
    };
    for (ll u = 0; u < n; u++) {
        if (adj[u].size() == 2) continue;
        assert(adj[u].size() == 1);
        dfs(u, u);
        break;
    }
    assert(ve.size() == n);
    vll wh(n, -15);
    for (ll i = 0; i < n; i++) wh[ve[i]] = i;
    SegTree st(n);
    for (ll i = 0; i < n; i++) st.update(i, ve[i]);
    vi ans(Q, -15);
    for (ll qid = 0; qid < Q; qid++) {
        assert(vl[qid] <= s[qid]);
        assert(e[qid] <= vr[qid]);
        assert(vl[qid] <= vr[qid]);
        assert(e[qid] != s[qid]);
        ll l1 = wh[s[qid]], r1 = wh[s[qid]];
        ll l2 = wh[e[qid]], r2 = wh[e[qid]];
        {ll l = -1;
        while (l+1 < l1) {
            ll mid = (l+l1)>>1;
            if (st.query(mid, r1).first >= vl[qid])
                l1 = mid;
            else
                l = mid;
        }}
        assert(st.query(l1, r1).first >= vl[qid]);
        {ll r = n;
        while (r1+1 < r) {
            ll mid = (r1+r)>>1;
            if (st.query(l1, mid).first >= vl[qid])
                r1 = mid;
            else
                r = mid;
        }}
        assert(st.query(l1, r1).first >= vl[qid]);
        {ll l = -1;
        while (l+1 < l2) {
            ll mid = (l+l2)>>1;
            if (st.query(mid, r2).second <= vr[qid])
                l2 = mid;
            else
                l = mid;
        }}
        assert(st.query(l2, r2).second <= vr[qid]);
        {ll r = n;
        while (r2+1 < r) {
            ll mid = (r2+r)>>1;
            if (st.query(l2, mid).second <= vr[qid])
                r2 = mid;
            else
                r = mid;
        }}
        assert(st.query(l2, r2).second <= vr[qid]);
        ans[qid] = 1;
        if (r1 < l2) ans[qid] = 0;
        if (r2 < l1) ans[qid] = 0;
    }
    return ans;
}

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

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:46:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (ll i = 0; i < us.size(); i++) {
      |                    ~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:2:
werewolf.cpp:64:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     assert(ve.size() == n);
      |            ~~~~~~~~~~^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51