oj.uz

Submission #772273

# Submission time Handle Problem Language Result Execution time Memory
772273 2023-07-03T21:01:40 Z PixelCat Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 42444 KB 
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "werewolf.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define F first
#define S second
using namespace std;
using pii = pair<int, int>;

const int MAXN = 200000;

struct DSU {
    int p[MAXN + 10];
    int rk[MAXN + 10];
    vector<int> adj[MAXN + 10];
    int l[MAXN + 10], r[MAXN + 10];
    int cur_id;

    void init(int n) {
        cur_id = 0;
        For(i, 0, n - 1) {
            adj[i].clear();
            l[i] = r[i] = i;
            p[i] = -1;
            rk[i] = 1;
        }
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return find(p[n]);
    }
    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return;
        if(rk[a] < rk[b]) swap(a, b);
        p[b] = a;
        adj[a].eb(b);
        rk[a] += rk[b];
        r[a] = r[b];
    }
    void dfs(int n, int *id) {
        id[n] = cur_id;
        cur_id++;
        for(auto &i:adj[n]) {
            dfs(i, id);
        }
    }
    void build_tree(int n, int *id) {
        For(i, 0, n - 1) if(p[i] < 0) {
            dfs(i, id);
        }
    }
    void out(int n) {
        cerr << "Tree:\n";
        For(i, 0, n - 1) cerr << p[i] << " \n"[i == n - 1];
        For(i, 0, n - 1) cerr << l[i] << " \n"[i == n - 1];
        For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
    }
} dsu;

#define LO(x) ((x) & (-(x)))
struct BIT {
    int n;
    int a[MAXN + 10];
    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        i++;
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
    }
    int ask(int i) {
        i++;
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
    int ask(int l, int r) {
        return ask(r - ask(l - 1));
    }
} bit;

struct Query {
    int s, e, l, r;
    int sl, sr, el, er;
    int ans;
};

struct SwpEvent {
    Query* qry;
    bool add;  // true for +, false for -
    int x;
};

vector<int> adj[MAXN + 10];
int px[MAXN + 10];
int py[MAXN + 10];
Query queries[MAXN + 10];

// stage 1: build trees & find ranges
void owo1(int n, int q) {
    vector<Query*> qrys(q);
    For(i, 0, q - 1) {
        qrys[i] = queries + i;
    }
    int ptr;

    sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
        return p1->l > p2->l;
    });
    ptr = 0;
    dsu.init(n);
    Forr(i, n - 1, 0) {
        for(auto &j:adj[i]) if(j > i) {
            dsu.uni(i, j);
        }
        while(ptr < q && qrys[ptr]->l == i) {
            auto &qry = *qrys[ptr];
            int rt = dsu.find(qry.s);
            qry.sl = dsu.l[rt];
            qry.sr = dsu.r[rt];
            ptr++;
        }
    }
    dsu.build_tree(n, px);
    For(i, 0, q - 1) {
        auto &qry = queries[i];
        qry.sl = px[qry.sl];
        qry.sr = px[qry.sr];
    }
    // dsu.out(n);

    sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
        return p1->r < p2->r;
    });
    ptr = 0;
    dsu.init(n);
    For(i, 0, n - 1) {
        for(auto &j:adj[i]) if(j < i) {
            dsu.uni(i, j);
        }
        while(ptr < q && qrys[ptr]->r == i) {
            auto &qry = *qrys[ptr];
            int rt = dsu.find(qry.e);
            qry.el = dsu.l[rt];
            qry.er = dsu.r[rt];
            ptr++;
        }
    }
    dsu.build_tree(n, py);
    For(i, 0, q - 1) {
        auto &qry = queries[i];
        qry.el = py[qry.el];
        qry.er = py[qry.er];
    }
    // dsu.out(n);

    // For(i, 0, q - 1) {
    //     auto &qry = queries[i];
    //     cerr << qry.sl << "," << qry.sr << "  " << qry.el << "," << qry.er << "\n";
    // }
}

// stage 2: do sweeping line
void owo2(int n, int q) {
    vector<SwpEvent> ev;
    For(i, 0, q - 1) {
        ev.push_back((SwpEvent){ queries + i, 0, queries[i].sl - 1 });
        ev.push_back((SwpEvent){ queries + i, 1, queries[i].sr });
    }
    sort(all(ev), [&](const SwpEvent &a, const SwpEvent &b) {
        return a.x < b.x;
    });
    int ptr = 0;
    while(ptr < sz(ev) && ev[ptr].x < 0) {
        ptr++;
    }

    vector<int> y(n, -1);
    For(i, 0, n - 1) {
        y[px[i]] = py[i];
        // cerr << px[i] << " " << py[i] << "\n";
    }

    bit.init(n);
    For(x, 0, n - 1) {
        bit.add(y[x], 1);
        while(ptr < sz(ev) && ev[ptr].x == x) {
            Query *qry = ev[ptr].qry;
            int res = bit.ask(qry->el, qry->er);
            if(ev[ptr].add) qry->ans += res;
            else qry->ans -= res;
            ptr++;
        }
    }
}

void owo2_slow(int n, int q) {
    For(idx, 0, q - 1) {
        auto &qry = queries[idx];
        bool ok = false;
        For(i, 0, n - 1) {
            if(qry.sl <= px[i] && px[i] <= qry.sr &&
               qry.el <= py[i] && py[i] <= qry.er) {
                ok = true;
                break;
            }
        }
        if(ok) qry.ans = 1;
        else qry.ans = 0;
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    int Q = sz(S);
    For(i, 0, sz(X) - 1) {
        int a = X[i], b = Y[i];
        adj[a].eb(b);
        adj[b].eb(a);
    }
    For(i, 0, Q - 1) {
        auto &qry = queries[i];
        qry.s = S[i];
        qry.e = E[i];
        qry.l = L[i];
        qry.r = R[i];
    }

    owo1(N, Q);
    // owo2(N, Q);
    owo2_slow(N, Q);

    vector<int> ans;
    For(i, 0, Q - 1) {
        ans.eb(queries[i].ans != 0);
    }
    return ans;
    
    // int Q = S.size();
    // vector<int> A(Q);
    // for (int i = 0; i < Q; ++i) {
    //     A[i] = 0;
    // }
    // return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9716 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9720 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9716 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9720 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 16 ms 10324 KB Output is correct
11 Correct 20 ms 10288 KB Output is correct
12 Correct 33 ms 10344 KB Output is correct
13 Correct 14 ms 10348 KB Output is correct
14 Correct 17 ms 10340 KB Output is correct
15 Correct 20 ms 10452 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9716 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9720 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 16 ms 10324 KB Output is correct
11 Correct 20 ms 10288 KB Output is correct
12 Correct 33 ms 10344 KB Output is correct
13 Correct 14 ms 10348 KB Output is correct
14 Correct 17 ms 10340 KB Output is correct
15 Correct 20 ms 10452 KB Output is correct
16 Execution timed out 4066 ms 42444 KB Time limit exceeded
17 Halted 0 ms 0 KB -