Submission #1307083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307083		fafnir	Werewolf (IOI18_werewolf)	C++20	15 / 100	484 ms	74724 KiB

werewolf

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

#define REP(i, n) for (int i = 0; i < (n); i++)


struct Tree2D {
    vector<pair<int,int>> pts;
    vector<vector<int>> nodes;
    int n = 0;

    Tree2D(const vector<pair<int,int>>& points) {
        pts = points;
        sort(pts.begin(), pts.end());

        n = pts.size();
        nodes.resize(4*n);

        build(0, 0, n-1);
    }

    void build(int u, int l, int r) {
        if (l == r) {
            nodes[u].push_back(pts[l].second);
        } else {
            int m = (l + r) / 2;
            build(2*u+1, l, m);
            build(2*u+2, m+1, r);
            nodes[u].reserve(r - l + 1);
            merge(nodes[2*u+1].begin(), nodes[2*u+1].end(),
                  nodes[2*u+2].begin(), nodes[2*u+2].end(),
                  back_inserter(nodes[u]));
        }
    }

    int countNode(int u, int yl, int yr) {
        // it0 --> First point at >= yl
        auto it0 = lower_bound(nodes[u].begin(), nodes[u].end(), yl);
        // it1 --> First element > yr
        auto it1 = upper_bound(nodes[u].begin(), nodes[u].end(), yr);
        return distance(it0, it1);
    }

    // qxl, qxr: Range of nodes in tree
    int query(int u, int l, int r, int qxl, int qxr, int qyl, int qyr) {
        if (r < qxl || l > qxr) {return 0;}
        if (l >= qxl && r <= qxr) {
            return countNode(u, qyl, qyr);
        }
        
        int m = (l + r) / 2;
        return query(2 * u + 1, l, m, qxl, qxr, qyl, qyr) +
               query(2 * u + 2, m + 1, r, qxl, qxr, qyl, qyr);
    }

    int query(int qxl, int qxr, int qyl, int qyr) {
        return query(0, 0, n-1, qxl, qxr, qyl, qyr);
    }

};


int fufind(vector<int>& fu, int x) {
    if (fu[x] < 0) {return x;}      // x is root
    fu[x] = fufind(fu, fu[x]);
    return fu[x];
}


// fu[u] := Parent node of u in DSU (or -1 if u is single node)
// tree[v] := left/right child nodes of v in Kruskal Reconstruction Tree
void fujoin(vector<int>& fu, vector<pair<int,int>>& tree, int x, int y) {
    x = fufind(fu, x);
    y = fufind(fu, y);

    if (x != y) {
        int p = fu.size();  // We add a new node

        fu[y] = p;
        fu[x] = p;
        
        fu.push_back(-1);   // Parent of p
        tree.push_back(make_pair(x,y));
    }
}


pair<int,int> dfs(vector<pair<int,int>>& tree, int v, int N, int& label) {
    // One of original nodes
    if (v < N) {
        tree[v].first = tree[v].second = label;
        label++;
    } else {
        pair<int,int> A = dfs(tree, tree[v].first, N, label);
        pair<int,int> B = dfs(tree, tree[v].second, N, label);
        tree[v].first = min(A.first, B.first);
        tree[v].second = max(A.second, B.second);
    }

    return make_pair(tree[v].first, tree[v].second);
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                            vector<int> S, vector<int> E,
                            vector<int> L, vector<int> R) {
    int Q = S.size();
    int M = X.size();
    
    vector<int> A(Q);
    vector<vector<int> > adj(N);
    REP(i, M) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<pair<int,int>> Lrange(Q);
    vector<pair<int,int>> Rrange(Q);
    vector<pair<int,int>> pts(N);
    

    // Compute Lrange
    {
        vector<int> fu(N);
        vector<int> idx(Q);
        vector<int> repr(Q);

        REP(i, N) {fu[i] = -1;}
        REP(i, Q) {idx[i] = i;}
        sort(idx.begin(), idx.end(), [&](int i0, int i1) {
            return L[i0] > L[i1];
        });
        vector<pair<int,int>> tree; tree.resize(N);
        int u = N-1;
        REP(i, Q) {
            int limit = L[idx[i]];
            for (; u >= limit; --u) {
                for (int v : adj[u]) {
                    if (v >= limit) {
                        fujoin(fu, tree, u, v);
                    }
                }
            }
            repr[idx[i]] = fufind(fu, S[idx[i]]);
        }    
        int label = 0;
        dfs(tree, tree.size()-1, N, label);
        REP(i, Q) {Lrange[idx[i]] = tree[repr[idx[i]]];}
        REP(i, N) {pts[i].first = tree[i].first;}
    }

    {
        vector<int> fu(N);
        vector<int> idx(Q);
        vector<int> repr(Q);

        REP(i, N) {fu[i] = -1;}
        REP(i, Q) {idx[i] = i;}
        sort(idx.begin(), idx.end(), [&](int i0, int i1) {
            return R[i0] < R[i1];
        });
        vector<pair<int,int>> tree; tree.resize(N);
        int u = 0;
        REP(i, Q) {
            int limit = R[idx[i]];
            for (; u <= limit; ++u) {
                for (int v : adj[u]) {
                    if (v <= limit) {
                        fujoin(fu, tree, u, v);
                    }
                }
            }
            repr[idx[i]] = fufind(fu, E[idx[i]]);
        }    
        int label = 0;
        dfs(tree, tree.size()-1, N, label);
        REP(i, Q) {Rrange[idx[i]] = tree[repr[idx[i]]];}
        REP(i, N) {pts[i].second = tree[i].second;}
    }

    Tree2D tree_2d(pts);
    REP(i, Q) {
        A[i] = tree_2d.query(Lrange[i].first, Lrange[i].second,
                             Rrange[i].first, Rrange[i].second) > 0;
    }

    return A;
}

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