oj.uz

Submission #800287

# Submission time Handle Problem Language Result Execution time Memory
800287 2023-08-01T13:06:36 Z Josia Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 38868 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;


vector<int> path;

void getPath(int v, int p, vector<vector<int>>& graph) {
    path.push_back(v);
    for (int i: graph[v]) {
        if (i == p) continue;
        getPath(i, v, graph);
    }
}





struct seg {
    struct node {
        int Min = -1e9, Max = 1e9;
    };

    node op(node a, node b) {
        node res;

        res.Min = min(a.Min, b.Min);
        res.Max = max(a.Max, b.Max);
        
        return res;
    }

    vector<node> tree;

    void update(int v, int rl, int rr, int pos, int val) {
        if (rl == rr) {
            tree[v].Min = val;
            tree[v].Max = val;
            return;
        }

        int rm = (rl + rr)/2;

        if (pos <= rm) update(v*2, rl, rm, pos, val);
        else update(v*2+1, rm+1, rr, pos, val);

        tree[v] = op(tree[v*2], tree[v*2+1]);
    }

    node query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return node();
        if (rl == ql && rr == qr) return tree[v];

        int rm = (rl + rr)/2;

        return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }

    void init(int n, vector<int> ass) {
        tree.resize(n*4);
        for (int i = 0; i<n; i++) {
            update(1, 0, n-1, i, ass[i]);
        }
    }
};




std::vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    path.clear();
    int M = X.size();
    int Q = S.size();

    vector<vector<int>> graph(N);

    for (int i = 0; i<M; i++) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    int v0 = -1;

    for (int i = 0; i<N; i++) {
        if (graph[i].size() == i) v0 = i;
    }

    getPath(v0, -1, graph);

    vector<int> pathInv(N);

    for (int i = 0; i<N; i++) pathInv[path[i]] = i;

    seg tree;
    tree.init(N, path);

    vector<int> res;

    for (int i = 0; i<Q; i++) {
        int startInd = pathInv[S[i]];
        int endInd = pathInv[E[i]];

        if (startInd<endInd) {
            int until;
            {
                int l = startInd;
                int r = N-1;
                while (l < r) {
                    int m = (l+r+1)/2;
                    if (tree.query(1, 0, N-1, startInd, m).Min >= L[i]) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                }
                until=l;
            }
            int from;
            {
                int l = 0;
                int r = endInd;
                while (l < r) {
                    int m = (l+r)/2;
                    if (tree.query(1, 0, N-1, m, endInd).Max <= R[i]) {
                        r = m;
                    } else {
                        l = m+1;
                    }
                }
                from = l;
            }

            if (until >= from) res.push_back(1);
            else res.push_back(0);
        }
        else {
            int until;
            {
                int l = 0;
                int r = startInd;
                while (l < r) {
                    int m = (l+r)/2;
                    if (tree.query(1, 0, N-1, m, startInd).Min >= L[i]) {
                        l = m;
                    } else {
                        r = m+1;
                    }
                }
                until=l;
            }
            int from;
            {
                int l = endInd;
                int r = N-1;
                while (l < r) {
                    int m = (l+r+1)/2;
                    if (tree.query(1, 0, N-1, endInd, m).Max <= R[i]) {
                        r = m;
                    } else {
                        l = m-1;
                    }
                }
                from = l;
            }

            if (until <= from) res.push_back(1);
            else res.push_back(0);
        }

    }

    return res;

}

Compilation message

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:87:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |         if (graph[i].size() == i) v0 = i;
      |             ~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 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 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 38868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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