oj.uz

Submission #612433

# Submission time Handle Problem Language Result Execution time Memory
612433 2022-07-29T14:57:21 Z fvogel499 Werewolf (IOI18_werewolf) C++17
100 / 100
 1620 ms 269712 KB 
// 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<<19;
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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39980 KB Output is correct
2 Correct 22 ms 39896 KB Output is correct
3 Correct 22 ms 39884 KB Output is correct
4 Correct 23 ms 39892 KB Output is correct
5 Correct 24 ms 39900 KB Output is correct
6 Correct 22 ms 39876 KB Output is correct
7 Correct 24 ms 39916 KB Output is correct
8 Correct 25 ms 39912 KB Output is correct
9 Correct 27 ms 39892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39980 KB Output is correct
2 Correct 22 ms 39896 KB Output is correct
3 Correct 22 ms 39884 KB Output is correct
4 Correct 23 ms 39892 KB Output is correct
5 Correct 24 ms 39900 KB Output is correct
6 Correct 22 ms 39876 KB Output is correct
7 Correct 24 ms 39916 KB Output is correct
8 Correct 25 ms 39912 KB Output is correct
9 Correct 27 ms 39892 KB Output is correct
10 Correct 32 ms 43128 KB Output is correct
11 Correct 31 ms 43084 KB Output is correct
12 Correct 29 ms 43084 KB Output is correct
13 Correct 29 ms 43092 KB Output is correct
14 Correct 30 ms 43100 KB Output is correct
15 Correct 30 ms 43260 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 257040 KB Output is correct
2 Correct 1567 ms 263816 KB Output is correct
3 Correct 1511 ms 259556 KB Output is correct
4 Correct 1532 ms 258468 KB Output is correct
5 Correct 1437 ms 259080 KB Output is correct
6 Correct 1474 ms 260780 KB Output is correct
7 Correct 1345 ms 258304 KB Output is correct
8 Correct 1504 ms 260804 KB Output is correct
9 Correct 1061 ms 255828 KB Output is correct
10 Correct 915 ms 257988 KB Output is correct
11 Correct 1049 ms 258304 KB Output is correct
12 Correct 966 ms 257428 KB Output is correct
13 Correct 1457 ms 257316 KB Output is correct
14 Correct 1574 ms 257332 KB Output is correct
15 Correct 1620 ms 257256 KB Output is correct
16 Correct 1559 ms 257440 KB Output is correct
17 Correct 1298 ms 259064 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39980 KB Output is correct
2 Correct 22 ms 39896 KB Output is correct
3 Correct 22 ms 39884 KB Output is correct
4 Correct 23 ms 39892 KB Output is correct
5 Correct 24 ms 39900 KB Output is correct
6 Correct 22 ms 39876 KB Output is correct
7 Correct 24 ms 39916 KB Output is correct
8 Correct 25 ms 39912 KB Output is correct
9 Correct 27 ms 39892 KB Output is correct
10 Correct 32 ms 43128 KB Output is correct
11 Correct 31 ms 43084 KB Output is correct
12 Correct 29 ms 43084 KB Output is correct
13 Correct 29 ms 43092 KB Output is correct
14 Correct 30 ms 43100 KB Output is correct
15 Correct 30 ms 43260 KB Output is correct
16 Correct 1343 ms 257040 KB Output is correct
17 Correct 1567 ms 263816 KB Output is correct
18 Correct 1511 ms 259556 KB Output is correct
19 Correct 1532 ms 258468 KB Output is correct
20 Correct 1437 ms 259080 KB Output is correct
21 Correct 1474 ms 260780 KB Output is correct
22 Correct 1345 ms 258304 KB Output is correct
23 Correct 1504 ms 260804 KB Output is correct
24 Correct 1061 ms 255828 KB Output is correct
25 Correct 915 ms 257988 KB Output is correct
26 Correct 1049 ms 258304 KB Output is correct
27 Correct 966 ms 257428 KB Output is correct
28 Correct 1457 ms 257316 KB Output is correct
29 Correct 1574 ms 257332 KB Output is correct
30 Correct 1620 ms 257256 KB Output is correct
31 Correct 1559 ms 257440 KB Output is correct
32 Correct 1298 ms 259064 KB Output is correct
33 Correct 1406 ms 264248 KB Output is correct
34 Correct 368 ms 99484 KB Output is correct
35 Correct 1601 ms 265296 KB Output is correct
36 Correct 1430 ms 263616 KB Output is correct
37 Correct 1560 ms 264888 KB Output is correct
38 Correct 1422 ms 263860 KB Output is correct
39 Correct 1438 ms 262404 KB Output is correct
40 Correct 1386 ms 269132 KB Output is correct
41 Correct 1289 ms 263104 KB Output is correct
42 Correct 857 ms 260220 KB Output is correct
43 Correct 1579 ms 268104 KB Output is correct
44 Correct 1344 ms 264756 KB Output is correct
45 Correct 1131 ms 261844 KB Output is correct
46 Correct 1295 ms 261476 KB Output is correct
47 Correct 1483 ms 260724 KB Output is correct
48 Correct 1467 ms 260424 KB Output is correct
49 Correct 1567 ms 260868 KB Output is correct
50 Correct 1545 ms 260056 KB Output is correct
51 Correct 1397 ms 269648 KB Output is correct
52 Correct 1400 ms 269712 KB Output is correct