Submission #833799

#	Time	Username	Problem	Language	Result	Execution time	Memory
833799		kamelfanger83	Werewolf (IOI18_werewolf)	C++17	0 / 100	584 ms	99360 KiB

werewolf

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>

//#include "werewolf.h"

using namespace std;

struct Unionfind{
    vector<int> group;
    Unionfind(int n){
        group.resize(n);
        iota(group.begin(), group.end(), 0);
    }
    int find(int i){
        if (i == group[i]) return i;
        return group[i] = find(group[i]);
    }
    void mergeBtA(int a, int b){
        a = find(a); b = find(b);
        if (a == b) return;
        group[b] = a;
    }
};

#define maxK 18

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    vector<vector<int>> cons (N);
    for (int i = 0; i < X.size(); ++i) {
        cons[X[i]].push_back(Y[i]);
        cons[Y[i]].push_back(X[i]);
    }
    vector<vector<int>> childrend (N);
    vector<int> parentd (N);
    vector<int[maxK]> parentTPd (N);
    vector<vector<int>> childrenu (N);
    vector<int> parentu (N);
    vector<int[maxK]> parentTPu (N);
    auto bT = [&cons, &N](bool down, vector<vector<int>> &fchildren, vector<int> &fparent, vector<int[maxK]> &fillTP){
        Unionfind unionfind (N);
        for (int i = down ? N - 1 : 0; down ? i >= 0 : i < N; i += down ? -1 : 1) {
            for (auto c : cons[i]){
                if (c > i && down || c < i && !down){
                    c = unionfind.find(c);
                    if (c == i) continue;
                    fparent[c] = i;
                    fchildren[i].push_back(c);
                    unionfind.mergeBtA(i, c);
                }
            }
            sort(fchildren[i].begin(), fchildren[i].end());
            fchildren[i].erase(unique(fchildren[i].begin(), fchildren[i].end()), fchildren[i].end());
        }
        for (int i = 0; i < N; ++i) {
            fillTP[i][0] = fparent[i];
        }
        for (int i = 1; i < maxK; ++i) {
            for (int j = 0; j < N; ++j) {
                fillTP[j][i] = fillTP[fillTP[j][i-1]][i-1];
            }
        }
    };
    bT(true, childrend, parentd, parentTPd);
    parentu[N-1] = N-1;
    bT(false, childrenu, parentu, parentTPu);
    vector<int> preorder (N, -1); int C = 0;
    vector<pair<int, int>> prerange (N); // inclusive, exclusive
    auto dfs = [&](auto &&self, int i) -> void{
        prerange[i].first = C;
        preorder[i] = C++;
        for (auto c : childrend[i]){
            self(self, c);
        }
        prerange[i].second = C;
    };
    for (int i = 0; i < N - 1; ++i) {
        if (preorder[i] == -1) dfs(dfs, i);
    }
    vector<set<int>> insubt (N);
    for (int i = 0; i < N; ++i) {
        insubt[i].insert(preorder[i]);
    }
    auto collect = [&](auto &&self, int i) -> void{
        for (auto c : childrenu[i]){
            if (insubt[c].size() > 1) self(self, c);
            if (insubt[c].size() > insubt[i].size()) swap(insubt[c], insubt[i]);
            for (auto ins : insubt[c]) insubt[i].insert(ins);
            insubt[c].clear();
        }
    };
    vector<int> Qind (S.size());
    iota(Qind.begin(), Qind.end(), 0);
    sort(Qind.begin(), Qind.end(), [&](int a, int b){return R[a] < R[b];});
    vector<int> res (S.size());
    for (auto ansi : Qind){
        int husubt = S[ansi];
        if (husubt < L[ansi]) {
            res[ansi] = 0;
            continue;
        }
        for (int i = maxK - 1; i >= 0; --i) {
            if (parentTPd[husubt][i] >= L[ansi]) husubt = parentTPd[husubt][i];
        }
        int wesubt = E[ansi];
        if (wesubt > R[ansi]){
            res[ansi] = 0;
            continue;
        }
        for (int i = maxK - 1; i >= 0; --i) {
            if (parentTPu[wesubt][i] <= R[ansi]) wesubt = parentTPu[wesubt][i];
        }
        collect(collect, wesubt);
        if (insubt[wesubt].lower_bound(prerange[husubt].first) != insubt[wesubt].end() && *insubt[wesubt].lower_bound(prerange[husubt].first) < prerange[husubt].second) res[ansi] = 1;
        else res[ansi] = 0;
    }
    return res;
}
/*
int main(){
    auto ret = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
    for (auto print : ret) cout << print << " ";
    return 0;
}*/

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < X.size(); ++i) {
      |                     ~~^~~~~~~~~~
werewolf.cpp: In lambda function:
werewolf.cpp:46:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |                 if (c > i && down || c < i && !down){
      |                     ~~~~~~^~~~~~~

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