oj.uz

Submission #936678

# Submission time Handle Problem Language Result Execution time Memory
936678 2024-03-02T13:56:15 Z haxorman Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 137132 KB 
#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;
}

void update(int ind, int val) {
    seg[ind+=SZ].push_back(val);
    
    while (ind /= 2) {
        seg[ind] = merge(seg[2*ind], seg[2*ind+1]);
    }
}

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;
};

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;
void dfs(int u, bool fl) {
    if (fl) rngr[u].first = cnt;
    else rngl[u].first = cnt;

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

    for (auto v : g2[u]) {
        dfs(v, fl);
    }

    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]};
    }
    sort(que, que+q, cmpl);

    int ind = 0, id = n;
    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) {
                g2[id].push_back(v);
                unite(id, v);
            }
        }
        ++id;

        while (que[ind].l >= cur) {
            rep[ind].first = find(que[ind].s);
            ++ind;
        }
    }
    cnt = 0;
    dfs(id-1, 0);
    for (int i = 0; i < id; ++i) {
        g2[i].clear();
    }

    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) {
                g2[id].push_back(v);
                unite(id, v);
            }
        }
        ++id;

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

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

Compilation message

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()) {
      |            ~~~~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 137132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 137132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4018 ms 105512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 137132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -