Submission #936780

#	Time	Username	Problem	Language	Result	Execution time	Memory
936780		haxorman	Werewolf (IOI18_werewolf)	C++14	100 / 100	606 ms	141656 KiB

werewolf

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

const int mxN = 4e5 + 7; 
const int SZ = exp2(ceil(log2(mxN)));

vector<int> seg[4*mxN];

vector<int> merge(vector<int> a, vector<int> b) {
    vector<int> res;
    int inda = 0, indb = 0;
    while (inda < a.size() && indb < b.size()) {
        if (a[inda] < b[indb]) {
            res.push_back(a[inda++]);
        }
        else {
            res.push_back(b[indb++]);
        }
    }

    while (inda < a.size()) {
        res.push_back(a[inda++]);
    }

    while (indb < b.size()) {
        res.push_back(b[indb++]);
    }

    return res;
}

bool query(int lo, int hi, int a, int b, int ind = 1, int l = 0, int r = SZ - 1) {
    if (lo > r || l > hi) {
        return false;
    }

    if (lo <= l && r <= hi) {
        auto it = lower_bound(seg[ind].begin(), seg[ind].end(), a);
        return it != seg[ind].end() && *it <= b;
    }

    int mid = (l+r)/2;
    return query(lo,hi,a,b,2*ind,l,mid) || query(lo,hi,a,b,2*ind+1,mid+1,r);
}

struct Query {
    int s, e, l, r, ind;
};

bool cmpl(Query a, Query b) {
    return a.l > b.l;
}

bool cmpr(Query a, Query b) {
    return a.r < b.r;
}

int n, m, q, dsu[mxN];
Query que[mxN];
pair<int,int> rngl[mxN], rngr[mxN], rep[mxN];
vector<int> g1[mxN], g2[mxN];

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
        return;
    }

    dsu[x] += dsu[y];
    dsu[y] = x;
}

int cnt;
bool fl;
void dfs(int u) {
    if (fl) rngr[u].first = cnt;
    else rngl[u].first = cnt;

    if (u < n) {
        ++cnt;
    }

    for (auto v : g2[u]) {
        dfs(v);
    }
    g2[u].clear();

    if (fl) rngr[u].second = cnt-1;
    else rngl[u].second = cnt-1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

    n = N, m = X.size(), q = S.size();
    for (int i = 0; i < m; ++i) {
        g1[X[i]].push_back(Y[i]);
        g1[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < q; ++i) {
        que[i] = {S[i], E[i], L[i], R[i], i};
    }
    
    int ind = 0, id = n;
    sort(que, que+q, cmpl);
    memset(dsu, -1, sizeof(dsu));
    for (int cur = n-1; cur >= 0; --cur) {
        g2[id].push_back(cur);
        unite(id, cur);
        
        for (auto v : g1[cur]) {
            if (v >= cur && find(v) != find(id)) {
                g2[id].push_back(find(v));
                unite(id, v);
            }
        }
        ++id;
        
        while (ind < q && que[ind].l >= cur) {
            rep[que[ind].ind].first = find(que[ind].s);
            ++ind;
        }
    }
    cnt = 0, fl = 0;
    dfs(id-1);

    ind = 0, id = n;
    sort(que, que+q, cmpr);
    memset(dsu, -1, sizeof(dsu));
    for (int cur = 0; cur <= n-1; ++cur) {
        g2[id].push_back(cur);
        unite(id, cur);

        for (auto v : g1[cur]) {
            if (v <= cur && find(v) != find(id)) {
                g2[id].push_back(find(v));
                unite(id, v);
            }
        }
        ++id;

        while (ind < q && que[ind].r <= cur) {
            rep[que[ind].ind].second = find(que[ind].e);
            ++ind;
        }
    }
    cnt = 0, fl = 1;
    dfs(id-1);

    /*
    for (int i = 0; i < n; ++i) {
        update(rngl[i].first, rngr[i].first);
    }
    */

    for (int i = 0; i < n; ++i) {
        seg[rngl[i].first+SZ].push_back(rngr[i].first);
    }

    for (int i = SZ-1; i >= 0; --i) {
        seg[i] = merge(seg[2*i], seg[2*i+1]);
    }

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        auto [a, b] = rep[que[i].ind];
        ans[que[i].ind] =
        query(rngl[a].first, rngl[a].second, rngr[b].first, rngr[b].second);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> merge(std::vector<int>, std::vector<int>)':
werewolf.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     while (inda < a.size() && indb < b.size()) {
      |            ~~~~~^~~~~~~~~~
werewolf.cpp:13:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     while (inda < a.size() && indb < b.size()) {
      |                               ~~~~~^~~~~~~~~~
werewolf.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while (inda < a.size()) {
      |            ~~~~~^~~~~~~~~~
werewolf.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (indb < b.size()) {
      |            ~~~~~^~~~~~~~~~
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:173:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |         auto [a, b] = rep[que[i].ind];
      |              ^

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