oj.uz

Submission #568542

# Submission time Handle Problem Language Result Execution time Memory
568542 2022-05-25T16:35:13 Z ngpin04 Werewolf (IOI18_werewolf) C++17
0 / 100
 420 ms 54724 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct DSU {
    bool rev;
    int n;
    vector <int> par,val;

    DSU(int _n = 0, bool _rev = 0) {
        rev = _rev;
        n = _n;
        par.assign(n + 5, -1);
        val.assign(n + 5, 0);
        iota(ALL(val), 0);
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
    }

    void join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return;
        par[u] += par[v];
        par[v] = u;
        if (!rev)
            maxi(val[u], val[v]);
        else
            mini(val[u], val[v]);
    }    

    int getval(int u) {
        return val[getpar(u)];
    }
};

vector <int> ed[N];
vector <int> qr[N];

int par[N];
int ans[N];
int mx[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,q;

void fix() {
    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    DSU pre(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) 
            t[ind] = pre.getval(t[ind]);
    }

    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    DSU suf(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i])
            suf.join(i, j);

        for (int ind : qr[i]) 
            s[ind] = suf.getval(s[ind]);
    }
}

void getans() {
    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    DSU pre(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) {
            if (t[ind] < l[ind] || s[ind] > r[ind])
                continue;
            ans[ind] |= pre.getpar(t[ind]) == pre.getpar(s[ind]);
        }
    }

    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    DSU suf(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i])
            suf.join(i, j);

        for (int ind : qr[i]) {
            if (t[ind] < l[ind] || s[ind] > r[ind])
                continue;
            ans[ind] |= suf.getpar(t[ind]) == suf.getpar(s[ind]);
        }
    }
}

void solve() {
    for (int i = 0; i < n - 1; i++) 
        if (x[i] > y[i])
            swap(x[i], y[i]);

    fix();
    getans();
}   

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;
    for (int i = 0; i < n - 1; i++)
        x[i] = X[i], y[i] = Y[i];

    q = S.size();
    for (int i = 0; i < q; i++) {
        s[i] = S[i];
        t[i] = E[i];
        l[i] = L[i];
        r[i] = R[i];
    }

    solve();
    vector <int> res;
    for (int i = 0; i < q; i++)
        res.push_back(ans[i]);
    return res;
}

//#include "grader.cpp"

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 420 ms 54724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -