oj.uz

Submission #772274

# Submission time Handle Problem Language Result Execution time Memory
772274 2023-07-03T21:05:29 Z PixelCat Werewolf (IOI18_werewolf) C++14
100 / 100
 326 ms 66612 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) {
        assert(y[x] >= 0);
        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);

    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 10452 KB Output is correct
2 Correct 5 ms 10536 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 4 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10420 KB Output is correct
8 Correct 5 ms 10420 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10536 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 4 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10420 KB Output is correct
8 Correct 5 ms 10420 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 8 ms 11220 KB Output is correct
11 Correct 8 ms 11220 KB Output is correct
12 Correct 7 ms 11220 KB Output is correct
13 Correct 7 ms 11220 KB Output is correct
14 Correct 8 ms 11220 KB Output is correct
15 Correct 8 ms 11268 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 51200 KB Output is correct
2 Correct 262 ms 59284 KB Output is correct
3 Correct 276 ms 59340 KB Output is correct
4 Correct 276 ms 59460 KB Output is correct
5 Correct 280 ms 59424 KB Output is correct
6 Correct 303 ms 59564 KB Output is correct
7 Correct 270 ms 59552 KB Output is correct
8 Correct 258 ms 59420 KB Output is correct
9 Correct 242 ms 59340 KB Output is correct
10 Correct 251 ms 59436 KB Output is correct
11 Correct 263 ms 59472 KB Output is correct
12 Correct 265 ms 59408 KB Output is correct
13 Correct 251 ms 57324 KB Output is correct
14 Correct 256 ms 57300 KB Output is correct
15 Correct 246 ms 57488 KB Output is correct
16 Correct 242 ms 57320 KB Output is correct
17 Correct 268 ms 59564 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10536 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 4 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10420 KB Output is correct
8 Correct 5 ms 10420 KB Output is correct
9 Correct 5 ms 10452 KB Output is correct
10 Correct 8 ms 11220 KB Output is correct
11 Correct 8 ms 11220 KB Output is correct
12 Correct 7 ms 11220 KB Output is correct
13 Correct 7 ms 11220 KB Output is correct
14 Correct 8 ms 11220 KB Output is correct
15 Correct 8 ms 11268 KB Output is correct
16 Correct 324 ms 51200 KB Output is correct
17 Correct 262 ms 59284 KB Output is correct
18 Correct 276 ms 59340 KB Output is correct
19 Correct 276 ms 59460 KB Output is correct
20 Correct 280 ms 59424 KB Output is correct
21 Correct 303 ms 59564 KB Output is correct
22 Correct 270 ms 59552 KB Output is correct
23 Correct 258 ms 59420 KB Output is correct
24 Correct 242 ms 59340 KB Output is correct
25 Correct 251 ms 59436 KB Output is correct
26 Correct 263 ms 59472 KB Output is correct
27 Correct 265 ms 59408 KB Output is correct
28 Correct 251 ms 57324 KB Output is correct
29 Correct 256 ms 57300 KB Output is correct
30 Correct 246 ms 57488 KB Output is correct
31 Correct 242 ms 57320 KB Output is correct
32 Correct 268 ms 59564 KB Output is correct
33 Correct 298 ms 59556 KB Output is correct
34 Correct 200 ms 57412 KB Output is correct
35 Correct 302 ms 60024 KB Output is correct
36 Correct 314 ms 59596 KB Output is correct
37 Correct 301 ms 59940 KB Output is correct
38 Correct 320 ms 59656 KB Output is correct
39 Correct 304 ms 59036 KB Output is correct
40 Correct 324 ms 66104 KB Output is correct
41 Correct 294 ms 59588 KB Output is correct
42 Correct 288 ms 59672 KB Output is correct
43 Correct 302 ms 62304 KB Output is correct
44 Correct 289 ms 59812 KB Output is correct
45 Correct 269 ms 59336 KB Output is correct
46 Correct 255 ms 59044 KB Output is correct
47 Correct 252 ms 57460 KB Output is correct
48 Correct 258 ms 57384 KB Output is correct
49 Correct 262 ms 57448 KB Output is correct
50 Correct 255 ms 57364 KB Output is correct
51 Correct 317 ms 66552 KB Output is correct
52 Correct 326 ms 66612 KB Output is correct