oj.uz

Submission #800323

# Submission time Handle Problem Language Result Execution time Memory
800323 2023-08-01T13:22:05 Z Josia Werewolf (IOI18_werewolf) C++17
34 / 100
 1760 ms 524288 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() == 1) v0 = i;
    }

    getPath(v0, -1, graph);

    // for (int i: path) cerr << i << " ";
    // cerr << "\n";

    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]];

        // cerr << startInd << " " << endInd << "\n";

        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;
            }
            // cerr << until << " " << from << "\n";
            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]) {
                        r = m;
                    } else {
                        l = 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]) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                }
                from = l;
            }

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

    }

    return res;

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1603 ms 43292 KB Output is correct
2 Correct 1760 ms 44552 KB Output is correct
3 Correct 1724 ms 44608 KB Output is correct
4 Correct 1702 ms 44600 KB Output is correct
5 Correct 1656 ms 44732 KB Output is correct
6 Correct 1628 ms 44732 KB Output is correct
7 Correct 1719 ms 44636 KB Output is correct
8 Correct 1658 ms 44636 KB Output is correct
9 Correct 970 ms 44616 KB Output is correct
10 Correct 1246 ms 44564 KB Output is correct
11 Correct 1395 ms 44632 KB Output is correct
12 Correct 1145 ms 44604 KB Output is correct
13 Correct 1689 ms 44676 KB Output is correct
14 Correct 1745 ms 44592 KB Output is correct
15 Correct 1687 ms 44640 KB Output is correct
16 Correct 1741 ms 44628 KB Output is correct
17 Correct 1640 ms 44780 KB Output is correct

Subtask #4
0 / 51.0

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