oj.uz

Submission #612405

# Submission time Handle Problem Language Result Execution time Memory
612405 2022-07-29T14:23:46 Z fvogel499 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 77252 KB 
// this code is bugged

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

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

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

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

std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
    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]);
    }
    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;
        }
    }
    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]]};
        while (range[i][0].f > 0 && ett[0][range[i][0].f-1] >= queryLB[i]) {
            range[i][0].f--;
        }
        while (range[i][0].s+1 < 2*n-1 && ett[0][range[i][0].s+1] >= queryLB[i]) {
            range[i][0].s++;
        }
    }
    for (int i = 0; i < nbQ; i++) {
        range[i][1] = {posOfInEtt[1][queryY[i]], posOfInEtt[1][queryY[i]]};
        while (range[i][1].f-1 > 0 && ett[1][range[i][1].f-1] <= queryRB[i]) {
            range[i][1].f--;
        }
        while (range[i][1].s+1 < 2*n-1 && ett[1][range[i][1].s+1] <= queryRB[i]) {
            range[i][1].s++;
        }
    }
    vector<int> res(nbQ, 0);
    for (int i = 0; i < nbQ; i++) {
        set<int> se;
        for (int j = range[i][0].f; j <= range[i][0].s; j++) {
            se.insert(ett[0][j]);
        }
        for (int j = range[i][1].f; j <= range[i][1].s; j++) {
            if (se.count(ett[1][j])) {
                res[i] = 1;
                break;
            }
        }
    }
    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:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     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:108:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |         assert(sz(ett[i]) == 2*n-1);
      |                           ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19092 KB Output is correct
5 Correct 11 ms 19128 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 10 ms 19024 KB Output is correct
8 Correct 10 ms 19096 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19092 KB Output is correct
5 Correct 11 ms 19128 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 10 ms 19024 KB Output is correct
8 Correct 10 ms 19096 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 681 ms 20052 KB Output is correct
11 Correct 450 ms 20020 KB Output is correct
12 Correct 38 ms 20008 KB Output is correct
13 Correct 313 ms 20212 KB Output is correct
14 Correct 48 ms 20180 KB Output is correct
15 Correct 621 ms 20156 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19092 KB Output is correct
5 Correct 11 ms 19128 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 10 ms 19024 KB Output is correct
8 Correct 10 ms 19096 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 681 ms 20052 KB Output is correct
11 Correct 450 ms 20020 KB Output is correct
12 Correct 38 ms 20008 KB Output is correct
13 Correct 313 ms 20212 KB Output is correct
14 Correct 48 ms 20180 KB Output is correct
15 Correct 621 ms 20156 KB Output is correct
16 Execution timed out 4073 ms 77252 KB Time limit exceeded
17 Halted 0 ms 0 KB -