oj.uz

Submission #1082319

# Submission time Handle Problem Language Result Execution time Memory
1082319 2024-08-31T06:52:46 Z jer033 Werewolf (IOI18_werewolf) C++17
34 / 100
 1172 ms 50420 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int NINF = -555'555'555;
const int INF  =  555'555'555;

class segTree{
public:
    int lef_index;
    int rig_index;
    int min_value;
    int max_value;
    segTree* lef_child;
    segTree* rig_child;

    segTree(vector<int> (&a), int l, int r)
    {
        lef_index = l;
        rig_index = r;
        if (l==r)
        {
            min_value = a[l];
            max_value = a[l];
            lef_child = nullptr;
            rig_child = nullptr;
        }
        else
        {
            int mid = (l+r)/2;
            lef_child = new segTree(a, l, mid);
            rig_child = new segTree(a, mid+1, r);
            min_value = min(lef_child->min_value, rig_child->min_value);
            max_value = max(lef_child->max_value, rig_child->max_value);
        }
    }

    int get_min(int l, int r)
    {
        int lef_overlap = max(l, lef_index);
        int rig_overlap = min(r, rig_index);
        if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
            return min_value;
        if (lef_overlap > rig_overlap)
            return INF;
        return min(lef_child->get_min(l, r), rig_child->get_min(l, r));
    }

    int get_max(int l, int r)
    {
        int lef_overlap = max(l, lef_index);
        int rig_overlap = min(r, rig_index);
        if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
            return max_value;
        if (lef_overlap > rig_overlap)
            return NINF;
        return max(lef_child->get_max(l, r), rig_child->get_max(l, r));
    }
};

int solve_query(int sloc, int eloc, int l, int r, segTree (&ST))
{
    if (sloc < eloc)
    {
        if (ST.get_min(sloc, eloc) >= l)
            return 1;
        else
        {
            int lo = sloc;
            int hi = eloc;
            while (lo!=hi)
            {
                int mid = (lo+hi+1)/2;
                if (ST.get_min(sloc, mid) >= l)
                    lo = mid;
                else
                    hi = mid-1;
            }
            //must be able to turn to wolf at lo
            if (ST.get_max(lo, eloc) <= r)
                return 1;
            return 0;
        }
    }
    else
    {
        if (ST.get_min(eloc, sloc) >= l)
            return 1;
        else
        {
            int lo = eloc;
            int hi = sloc;
            while (lo!=hi)
            {
                //finding the lowest value I can remain human in
                int mid = (lo+hi)/2;
                if (ST.get_min(mid, sloc) >= l)
                    hi = mid;
                else
                    lo = mid+1;
            }
            //must be able to turn to wolf at lo
            if (ST.get_max(eloc, lo) <= r)
                return 1;
            return 0;
        }
    }
}

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) {
    //preprocessing
    vector<vector<int>> edges(N);
    int M = X.size();
    for (int i=0; i<M; i++)
    {
        int x = X[i];
        int y = Y[i];
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    //create the line graph
    int leaf = -1;
    for (int i=0; i<N; i++)
        if (edges[i].size() == 1)
            leaf = i;
    vector<int> line;
    int prev = leaf;
    int curr = edges[leaf][0];
    line.push_back(leaf);
    line.push_back(curr);
    while (edges[curr].size() == 2)
    {
        int nex;
        for (int i: edges[curr])
            if (i!=prev)
                nex = i;
        line.push_back(nex);
        prev = curr;
        curr = nex;
    }

    vector<int> refs(N);
    for (int i=0; i<N; i++)
        refs[line[i]] = i;

    segTree ST = segTree(line, 0, N-1);

    int Q = S.size();
    std::vector<int> answers(Q);

    for (int i = 0; i < Q; i++) {
        int l = L[i];
        int r = R[i];
        int s = S[i];
        int e = E[i];
        int sloc = refs[s];
        int eloc = refs[e];
        answers[i] = solve_query(sloc, eloc, l, r, ST);
    }
    return answers;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 50308 KB Output is correct
2 Correct 510 ms 50372 KB Output is correct
3 Correct 500 ms 50116 KB Output is correct
4 Correct 786 ms 50304 KB Output is correct
5 Correct 894 ms 50116 KB Output is correct
6 Correct 1160 ms 50368 KB Output is correct
7 Correct 1172 ms 50308 KB Output is correct
8 Correct 515 ms 50372 KB Output is correct
9 Correct 312 ms 50180 KB Output is correct
10 Correct 214 ms 50176 KB Output is correct
11 Correct 292 ms 50184 KB Output is correct
12 Correct 507 ms 50372 KB Output is correct
13 Correct 846 ms 50420 KB Output is correct
14 Correct 838 ms 50372 KB Output is correct
15 Correct 858 ms 50120 KB Output is correct
16 Correct 860 ms 50248 KB Output is correct
17 Correct 1125 ms 50120 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -