Submission #1077915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077915		asdasdqwer	Werewolf (IOI18_werewolf)	C++14	49 / 100	293 ms	72440 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

struct DMin {
    vector<int> p, r;

    DMin(int n, vector<int> &pr) : p(n) {
        for (int i=0;i<n;i++) {
            p[i]=i;
        }
        r=pr;
    }

    int get(int i) {
        if (i != p[i])p[i]=get(p[i]);
        return p[i];
    }

    void unite(int a, int b) {
        a=get(a);b=get(b);
        if (r[a] > r[b])swap(a,b);
        p[b]=a;
    }
};

struct DMax {
    vector<int> p, r;

    DMax(int n, vector<int> &pr) : p(n) {
        for (int i=0;i<n;i++) {
            p[i]=i;
        }
        r=pr;
    }

    int get(int i) {
        if (i != p[i])p[i]=get(p[i]);
        return p[i];
    }

    void unite(int a, int b) {
        a=get(a);b=get(b);
        if (r[a] < r[b])swap(a,b);
        p[b]=a;
    }
};


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) {
    vector<vector<int>> g(N);
    int M = X.size(), Q=S.size();
    for (int i=0;i<M;i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int> ans(Q,0);
    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        for (int i=0;i<Q;i++) {
            vector<bool> vis1(N, false), vis2(N, false);
            function<void(int)> dfs1=[&](int node) {
                vis1[node]=true;
                for (auto &x:g[node]) {
                    if (x >= L[i] && !vis1[x]) dfs1(x);
                }
            };

            function<void(int)> dfs2=[&](int node) {
                vis2[node]=true;
                for (auto &x:g[node]) {
                    if (x <= R[i] && !vis2[x]) dfs2(x);
                }
            };

            dfs1(S[i]);dfs2(E[i]);
            for (int j=L[i];j<=R[i];j++) {
                if (vis1[j] && vis2[j]) {
                    ans[i]=true;break;
                }
            }
        }
        return ans;
    }

    // first find node with degree one
    int node = -1;
    for (int i=0;i<N;i++) {
        if (g[i].size() == 1) node = i;
    }

    vector<int> order(N, 0);
    function<void(int,int)> dfs=[&](int nd, int parent) {
        for (auto &x:g[nd]) {
            if (x == parent) continue;
            order[x] = order[nd]+1;
            dfs(x, nd);
        }
    };

    dfs(node, -1);

    DMin dmn(N, order);
    DMax dmx(N, order);

    vector<int> far(Q, -1);
    vector<vector<int>> newl(N), newr(N);
    for (int i=0;i<Q;i++) {
        newl[L[i]].push_back(i);
        newr[R[i]].push_back(i);
    }
    for (int i=N-1;i>=0;i--) {
        for (auto &x:g[i]) {
            if (x > i) {
                dmn.unite(x, i);
                dmx.unite(x, i);
            }
        }

        for (auto &x : newl[i]) {
            if (order[S[x]] < order[E[x]]) {
                far[x] = dmx.get(S[x]);
            }

            else {
                far[x] = dmn.get(S[x]);
            }
        }
    }

    DMin dmn2(N, order);
    DMax dmx2(N, order);
    for (int i=0;i<N;i++) {
        for (auto &x:g[i]) {
            if (x < i) {
                dmn2.unite(x, i);
                dmx2.unite(x, i);
            }
        }

        for (auto &x : newr[i]) {
            int far2;
            if (order[S[x]] < order[E[x]]) {
                far2 = dmn2.get(E[x]);
                if (order[far[x]] >= order[far2]) ans[x]=true;
            }

            else {
                far2 = dmx2.get(E[x]);
                if (order[far[x]] <= order[far2]) ans[x]=true;
            }
        }
    }

    return ans;
}

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