oj.uz

Submission #1018317

# Submission time Handle Problem Language Result Execution time Memory
1018317 2024-07-09T18:52:03 Z vjudge1 Werewolf (IOI18_werewolf) C++17
34 / 100
 1425 ms 52156 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 11868 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 11868 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 52156 KB Output is correct
2 Correct 1199 ms 51656 KB Output is correct
3 Correct 1208 ms 51896 KB Output is correct
4 Correct 1096 ms 51892 KB Output is correct
5 Correct 1149 ms 51832 KB Output is correct
6 Correct 961 ms 52012 KB Output is correct
7 Correct 1026 ms 51648 KB Output is correct
8 Correct 1199 ms 51804 KB Output is correct
9 Correct 487 ms 51800 KB Output is correct
10 Correct 919 ms 51904 KB Output is correct
11 Correct 956 ms 51736 KB Output is correct
12 Correct 463 ms 51648 KB Output is correct
13 Correct 1293 ms 51896 KB Output is correct
14 Correct 1298 ms 51648 KB Output is correct
15 Correct 1316 ms 51896 KB Output is correct
16 Correct 1425 ms 51904 KB Output is correct
17 Correct 1252 ms 51648 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 11868 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -