Submission #612428

#	Time	Username	Problem	Language	Result	Execution time	Memory
612428		fvogel499	Werewolf (IOI18_werewolf)	C++17	15 / 100	1475 ms	486728 KiB

werewolf

// this code is bugged

#include "werewolf.h"
#include <bits/stdc++.h>

#define int long long

#define sz(x) ((x).size())

#define mp pair<pii, pii>
#define pii pair<int, int>
#define f first
#define s second

using namespace std;

const int inf = 1e9;
const int p2 = 1<<18;
const int siz = 4e5+40;
const int LG = 20;

struct Segtree {
    Segtree() {
        t = new int [p2*2];
        cls();
    }
    ~Segtree() {
        delete [] t;
    }
    void cls() {
        for (int i = 0; i < p2*2; i++) t[i] = 0;
    }
    void upd(int x, int v) {
        for (x += p2; x; x /= 2) {
            t[x] += v;
        }
    }
    int get(int b, int e) {
        int r = 0;
        b += p2;
        e += p2;
        while (b <= e) {
            if (b%2 == 1) {
                r += t[b];
                b++;
            }
            if (e%2 == 0) {
                r += t[e];
                e--;
            }
            b /= 2;
            e /= 2;
        }
        return r;
    }
    int* t;
};

vector<int> order [2];
vector<int> graph [2][siz];
vector<int> ett [2];
int posOfInEtt [2][siz];
int dsu [siz];
int jmp [2][siz][LG];
int smallerP2 [siz];
vector<int> posInOne [siz];

int gp(int x) {
    if (dsu[x] == x) return x;
    return dsu[x] = gp(dsu[x]);
}

bool merge(int x, int y) {
    x = gp(x);
    y = gp(y);
    if (x == y) return false;
    dsu[y] = x;
    return true;
}

void dfs(int T, int x, int p = -1) {
    ett[T].push_back(x);
    for (int y : graph[T][x]) if (y != p) {
        dfs(T, y, x);
        ett[T].push_back(x);
    }
}

int min(int x, int y) {
    return x < y ? x : y;
}

int max(int x, int y) {
    return x > y ? x : y;
}

int getMinZero(int start, int end) {
    int power = smallerP2[end-start+1];
    return min(jmp[0][start][power], jmp[0][end-(1<<power)+1][power]);
}

int getMaxOne(int start, int end) {
    int power = smallerP2[end-start+1];
    return max(jmp[1][start][power], jmp[1][end-(1<<power)+1][power]);
}

std::vector<signed> check_validity(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, std::vector<signed> queryX, std::vector<signed> queryY, std::vector<signed> queryLB, std::vector<signed> queryRB) {
    for (int i = 0; i < siz; i++) {
        smallerP2[i] = 0;
        while ((1<<(smallerP2[i]+1)) <= i) {
            smallerP2[i]++;
        }
    }
    vector<int> adj [n];
    for (int i = 0; i < sz(edgeX); i++) {
        adj[edgeX[i]].push_back(edgeY[i]);
        adj[edgeY[i]].push_back(edgeX[i]);
    }
    typedef int (*CompFunct) (int a, int b);
    CompFunct funct [2] = {min, max};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) order[i].push_back(j);
        if (i == 1) reverse(order[i].begin(), order[i].end());
        for (int j = 0; j < n; j++) dsu[j] = j;
        bool seen [n];
        for (int j = 0; j < n; j++) seen[j] = false;
        for (int jIdx = n-1; jIdx >= 0; jIdx--) {
            int j = order[i][jIdx];
            for (int k : adj[j]) if (seen[k]) {
                int pJ = gp(j);
                int pK = gp(k);
                if (pJ != pK) {
                    graph[i][pJ].push_back(pK);
                    graph[i][pK].push_back(pJ);
                    assert(merge(pJ, pK));
                }
            }
            seen[j] = true;
        }
        dfs(i, order[i][0]);
        assert(sz(ett[i]) == 2*n-1);
        for (int j = 0; j < 2*n-1; j++) {
            posOfInEtt[i][ett[i][j]] = j;
        }
        for (int j = 0; j < 2*n-1; j++) jmp[i][j][0] = ett[i][j];
        for (int j = 1; j < LG; j++) {
            for (int k = 0; k < 2*n-1; k++) {
                if (k+(1<<(j-1)) >= 2*n-1) {
                    jmp[i][k][j] = jmp[i][k][j-1];
                }
                else {
                    jmp[i][k][j] = funct[i](jmp[i][k][j-1], jmp[i][k+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    const int nbQ = sz(queryX);
    pii range [nbQ][2];
    for (int i = 0; i < nbQ; i++) {
        range[i][0] = {posOfInEtt[0][queryX[i]], posOfInEtt[0][queryX[i]]};
        for (int j = p2; j; j /= 2) {
            int prop = range[i][0].f-j;
            if (prop < 0) continue;
            if (getMinZero(prop, range[i][0].s) >= queryLB[i]) {
                range[i][0].f = prop;
            }
        }
        for (int j = p2; j; j /= 2) {
            int prop = range[i][0].s+j;
            if (prop >= 2*n-1) continue;
            if (getMinZero(range[i][0].f, prop) >= queryLB[i]) {
                range[i][0].s = prop;
            }
        }
    }
    for (int i = 0; i < nbQ; i++) {
        range[i][1] = {posOfInEtt[1][queryY[i]], posOfInEtt[1][queryY[i]]};
        for (int j = p2; j; j /= 2) {
            int prop = range[i][1].f-j;
            if (prop < 0) continue;
            if (getMaxOne(prop, range[i][1].s) <= queryRB[i]) {
                range[i][1].f = prop;
            }
        }
        for (int j = p2; j; j /= 2) {
            int prop = range[i][1].s+j;
            if (prop >= 2*n-1) continue;
            if (getMaxOne(range[i][1].f, prop) <= queryRB[i]) {
                range[i][1].s = prop;
            }
        }
    }
    vector<mp> qAt [n*2-1];
    for (int i = 0; i < nbQ; i++) {
        qAt[range[i][0].s].push_back({range[i][1], {i, 1}});
        if (range[i][0].f-1 >= 0) {
            qAt[range[i][0].f-1].push_back({range[i][1], {i, -1}});
        }
    }
    int cnt [nbQ];
    for (int i = 0; i < nbQ; i++) cnt[i] = 0;
    Segtree st = Segtree();
    for (int i = 0; i < 2*n-1; i++) {
        posInOne[ett[1][i]].push_back(i);
    }
    for (int i = 0; i < 2*n-1; i++) {
        for (int j : posInOne[ett[0][i]]) {
            st.upd(j, 1);
        }
        for (mp j : qAt[i]) {
            cnt[j.s.f] += j.s.s*st.get(j.f.f, j.f.s);
        }
    }
    vector<signed> res(nbQ, 0);
    for (int i = 0; i < nbQ; i++) {
        if (cnt[i] >= 1) {
            res[i] = 1;
        }
    }
    return res;
}

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:115:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < sz(edgeX); i++) {
      |                       ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:4:
werewolf.cpp:141:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |         assert(sz(ett[i]) == 2*n-1);
      |                           ^

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