oj.uz

Submission #727877

# Submission time Handle Problem Language Result Execution time Memory
727877 2023-04-21T14:08:45 Z nguyentunglam Werewolf (IOI18_werewolf) C++17
0 / 100
 517 ms 268708 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;

const int N = 4e5 + 10;
vector<ii> e1[N], e2[N];
int cnt;
vector<tuple<int, int, int, int> > query[N];

struct kruskal {
    int par[20][N], w[N], timer, lst[N];
    int st[N], ed[N];
    vector<int> ad[N];

    int root(int v) {
        return par[0][v] < 0 ? v : par[0][v] = root(par[0][v]);
    }

    void join(int u, int v, int c) {
        u = root(u); v = root(v);
        if (u == v) return;
        ++cnt;
        ad[cnt].push_back(u);
        ad[cnt].push_back(v);
        par[0][cnt] = -1; w[cnt] = c;
        par[0][u] = cnt; par[0][v] = cnt;
    }

    void dfs(int u) {
        st[u] = ++timer;
        lst[timer] = u;
        for(int j = 1; j <= 17; j++) par[j][u] = par[j - 1][par[j - 1][u]];
        for(int &v : ad[u]) {
            par[0][v] = u;
            dfs(v);
        }
        ed[u] = timer;
    }

    int get(int u, int cost, int type) {
        for(int j = 18; j >= 0; j--) {
            int p = par[j][u];
            if (p <= 0) continue;
            if (!type && w[p] <= cost) u = p;
            else if (type && w[p] >= cost) u = p;
        }
        return u;
    }

} T[2];

int bit[N];
void up(int pos, int val) {
    while (pos <= 4e5) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

int getrange(int l, int r) {
    return get(r) - get(l - 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) {\
    cnt = n - 1;

    for(int i = 0; i < x.size(); i++) {
        int u = x[i], v = y[i];
        e1[min(u, v)].emplace_back(u, v);
        e2[max(u, v)].emplace_back(u, v);
    }

    for(int i = 0; i < n; i++) T[0].par[0][i] = T[1].par[0][i] = -1;

    for(int i = 0; i < n; i++) for(auto &it : e2[i]) {
        T[0].join(it.fi, it.se, i);
//        cout << it.fi << " " << it.se << " " << i << " " << cnt << " " << par[0][2] << endl;
    }
    T[0].dfs(cnt);

    for(int i = n - 1; i >= 0; i--) for(auto &it : e1[i]) {
        T[1].join(it.fi, it.se, i);
    }
    T[1].dfs(cnt);
//    cout << T[0].par[0][2] << " " << endl;
    vector<int> ans;
    ans.resize(s.size());
//    for(int i = 1; i <= T[0].timer; i++) cout << T[0].lst[i] << " "; cout << endl;
//    for(int i = 1; i <= T[1].timer; i++) cout << T[1].lst[i] << " "; cout << endl;

    for(int i = 0; i < s.size(); i++) {
        int p1 = T[1].get(s[i], l[i], 1);
        int p2 = T[0].get(e[i], r[i], 0);
//        cout << p1 << " " << p2 << endl;
//        cout << T[1].st[p1] << " " << T[1].ed[p1] << " " << T[0].st[p2] << " " << T[0].ed[p2] << endl;
        query[T[1].ed[p1]].emplace_back(T[0].st[p2], T[0].ed[p2], i, 1);
        query[T[1].st[p1] - 1].emplace_back(T[0].st[p2], T[0].ed[p2], i, -1);
    }

    for(int i = 0; i <= T[1].timer; i++) {
        int u = T[1].lst[i];
        if (u < n) up(T[0].st[u], 1);
        for(auto &it : query[i]) {
            int L, R, id, sign; tie(L, R, id, sign) = it;
            ans[id] += sign * getrange(L, R);
        }
    }

    for(int &i : ans) {
        i = (i > 0);
    }
    return ans;
}

#ifdef ngu
int main() {
//    vector<int> ret = check_validity(4, {0, 1, 2, 3}, {1, 2, 3, 0}, {0}, {2}, {2}, {1});
    vector<int> ret = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
}
#endif // ngu

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:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47596 KB Output is correct
2 Incorrect 27 ms 47672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47596 KB Output is correct
2 Incorrect 27 ms 47672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47596 KB Output is correct
2 Incorrect 27 ms 47672 KB Output isn't correct
3 Halted 0 ms 0 KB -