Submission #122852

#	Time	Username	Problem	Language	Result	Execution time	Memory
122852		Vlatko	Werewolf (IOI18_werewolf)	C++14	49 / 100	520 ms	40688 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;


const int maxn = 200010;

int N, M, Q, S, E, L, R;
vector<int> adj[maxn];

int line[maxn];
int lineidx[maxn];

void dfs(int u, int p, vector<int>& vec) {
    vec.push_back(u);
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u, vec);
        }
    }
}

pii tree[4*maxn];

inline void merge(pii& v, pii& l, pii& r) {
    v.first = min(l.first, r.first);
    v.second = max(l.second, r.second);
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v].first = tree[v].second = line[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        merge(tree[v], tree[2*v], tree[2*v+1]);
    }
}

pii getrange(int v, int tl, int tr, int idx, bool type) {
    if (type == false ? tree[v].first >= L : tree[v].second <= R) {
        return pii(tl, tr);
    } else if (tl == tr) {
        return pii(-1, -1);
    } else {
        int tm = (tl + tr) / 2;
        if (idx <= tm) { // target is on left side
            pii res1 = getrange(2*v, tl, tm, idx, type);
            if (res1.first == -1) {
                return pii(-1, -1);
            } else if (res1.second < tm) { // didn't reach right child
                return res1;
            } else { // may expand to right side
                pii res2 = getrange(2*v+1, tm+1, tr, tm+1, type);
                if (res2.first == -1) {
                    return res1;
                } else {
                    return pii(res1.first, res2.second);
                }
            }
        } else { // target is on right side
            pii res1 = getrange(2*v+1, tm+1, tr, idx, type);
            if (res1.first == -1) {
                return pii(-1, -1);
            } else if (res1.first > tm+1) { // didn't reach left child
                return res1;
            } else { // may expand to left side
                pii res2 = getrange(2*v, tl, tm, tm, type);
                if (res2.first == -1) {
                    return res1;
                } else {
                    return pii(res2.first, res1.second);
                }
            }
        }
    }
}

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) {
    N = _N;
    M = _X.size();
    Q = _S.size();
    vector<int> A(Q);
    for (int i = 0; i < M; ++i) {
        adj[_X[i]].push_back(_Y[i]);
        adj[_Y[i]].push_back(_X[i]);
    }
    if (N <= 3000 || M > N-1) {
        vector<int> status(N);
        for (int query = 0; query < Q; ++query) {
            S = _S[query], E = _E[query], L = _L[query], R = _R[query];
            status.assign(N, 0);
            queue<int> q;
            if (S >= L) {
                q.push(S);
                status[S] |= 1;
            }
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : adj[u]) {
                    if (v >= L && status[v] == 0) {
                        status[v] |= 1;
                        q.push(v);
                    }
                }
            }
            int intersection = -1;
            if (E <= R) {
                q.push(E);
                status[E] |= 2;
            }
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                if (status[u] == 3) {
                    intersection = u;
                    break;
                }
                for (int v : adj[u]) {
                    if (v <= R && (status[v] == 0 || status[v] == 1)) {
                        status[v] |= 2;
                        q.push(v);
                    }
                }
            }
            if (intersection == -1) {
                A[query] = 0;
            } else {
                A[query] = 1;
            }
        }
    } else {
        vector<int> v1, v2;
        if (adj[0].size() == 1) {
            dfs(adj[0][0], 0, v1);
        } else {
            dfs(adj[0][0], 0, v1);
            dfs(adj[0][1], 0, v2);
        }
        reverse(v1.begin(), v1.end());
        for (int i = 0; i < (int)v1.size(); ++i) {
            line[i] = v1[i];
        }
        line[v1.size()] = 0;
        for (int i = 0; i < (int)v2.size(); ++i) {
            line[v1.size()+1+i] = v2[i];
        }
        for (int i = 0; i < N; ++i) {
            lineidx[line[i]] = i;
        }
//        cout << "line: ";
//        for (int i = 0; i < N; ++i) {
//            cout << line[i] << ' ';
//        }
//        cout << '\n';
        build(1, 0, N-1);
        for (int query = 0; query < Q; ++query) {
            S = _S[query], E = _E[query], L = _L[query], R = _R[query];
            pii range1 = getrange(1, 0, N-1, lineidx[S], false);
            pii range2 = getrange(1, 0, N-1, lineidx[E], true);
            int l = max(range1.first, range2.first);
            int r = min(range1.second, range2.second);
//            cout << "S=" << S << " E=" << E << " L=" << L << " R=" << R << "\n";
//            cout << "Srange=[" << range1.first << "," << range1.second << "]\n";
//            cout << "Erange=[" << range2.first << "," << range2.second << "]\n";
            if (l <= r && range1 != pii(-1, -1) && range2 != pii(-1, -1)) {
                A[query] = 1;
            } else {
                A[query] = 0;
            }
        }
    }
    return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51