Submission #800323

#	Time	Username	Problem	Language	Result	Execution time	Memory
800323		Josia	늑대인간 (IOI18_werewolf)	C++17	34 / 100	1760 ms	524288 KiB

werewolf

#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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51