oj.uz

Submission #938957

# Submission time Handle Problem Language Result Execution time Memory
938957 2024-03-06T01:32:24 Z LOLOLO Werewolf (IOI18_werewolf) C++17
15 / 100
 534 ms 136360 KB 
//#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100, M = 1e7 + 10;
vector <pair <int, int>> edge[N], inc[N], dcs[N], edge2[N];
int idl[N], idr[N], l1[N], r1[N], l2[N], r2[N], id[N * 5], pos[N], L[N], R[N], val[N];
ll f[N];
void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;  
}

int range(int l, int r) {
    return get(r) - get(l - 1);
}

vector < vector <int>> save[N];

vector <int> solve(vector <int> &p, vector <int> &q, int num) {
    int n = sz(q) - 1;
    for (int i = 1; i <= n; i++)
        pos[p[i]] = i;

    int cnt = 0;
    for (int i = 0; i < num; i++) {
        save[r2[i]].pb({l1[i], r1[i], cnt});
        L[i] = cnt;
        cnt++;
        save[l2[i] - 1].pb({l1[i], r1[i], cnt});
        R[i] = cnt;
        cnt++;
    }

    for (int i = 1; i <= n; i++) {
        int x = q[i];
        upd(pos[x], 1);

        for (auto x : save[i]) {
            val[x[2]] = range(x[0], x[1]);
        }
    }

    vector <int> ans;
    for (int i = 0; i < num; i++) {
        int v = val[R[i]] - val[L[i]];
        if (v) {
            ans.pb(1);
        } else {
            ans.pb(0);
        }
    }

    return ans;
}

struct kruskal_tree{
    int n;
    vector <int> par, arr, in, ou;
    vector < vector <int>> ed;

    void dfs(int u) {
        bool is = 0;
        in[u] = sz(arr);
        for (auto x : ed[u]) {
            dfs(x);
            is = 1;
        }

        if (is == 0) {
            arr.pb(u);
        }
        ou[u] = sz(arr) - 1;
    }

    void assign(int N) {
        arr.pb(0);
        n = N;
        par.assign(2 * n + 10, 0);
        in.assign(2 * n + 10, 0);
        ou.assign(2 * n + 10, 0);
        ed.resize(2 * n + 10);
        for (int i = 1; i <= n * 2; i++)
            par[i] = i;
    }

    int find(int u) {
        return par[u] == u ? u : find(par[u]);
    }

    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) 
            return;

        n++;
        par[a] = par[b] = par[n] = n;
        ed[n].pb(a);
        ed[n].pb(b);
    }
};

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 m = sz(x);
    int n = N;
    for (int i = 0; i < m; i++) {
        x[i]++, y[i]++;
        edge[max(x[i], y[i])].pb({x[i], y[i]});
        edge2[min(x[i], y[i])].pb({x[i], y[i]});
    }

    kruskal_tree A, B;
    A.assign(n);
    B.assign(n);

    int q = sz(s);
    for (int i = 0; i < q; i++) {
        l[i]++;
        r[i]++;
        s[i]++;
        e[i]++;
        inc[r[i]].pb({e[i], i});
        dcs[l[i]].pb({s[i], i});
    }

    for (int i = 1; i <= n; i++) {
        for (auto x : edge[i]) {
            A.unite(x.f, x.s);
        }

        for (auto x : inc[i]) {
            idl[x.s] = A.find(x.f);
        }
    }

    for (int i = n; i >= 1; i--) {
        for (auto x : edge2[i]) {
            B.unite(x.f, x.s);
        }

        for (auto x : dcs[i]) {
            idr[x.s] = B.find(x.f);
        }
    }

    A.dfs(A.n);
    B.dfs(B.n);

    for (int i = 0; i < q; i++) {
        l1[i] = A.in[idl[i]];
        r1[i] = A.ou[idl[i]];
        l2[i] = B.in[idr[i]];
        r2[i] = B.ou[idr[i]];
        //cout << l1[i] << ' ' << r1[i] << ' ' << l2[i] << ' ' << r2[i] << '\n';
    }

    return solve(A.arr, B.arr, q);
}

/*int main() {
    auto v = 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});
    for (auto x : v)
        cout << x << " ";

    cout << '\n';    
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35184 KB Output is correct
4 Correct 9 ms 35188 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 8 ms 35248 KB Output is correct
7 Correct 9 ms 35164 KB Output is correct
8 Correct 7 ms 35164 KB Output is correct
9 Correct 8 ms 35164 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35184 KB Output is correct
4 Correct 9 ms 35188 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 8 ms 35248 KB Output is correct
7 Correct 9 ms 35164 KB Output is correct
8 Correct 7 ms 35164 KB Output is correct
9 Correct 8 ms 35164 KB Output is correct
10 Correct 17 ms 36700 KB Output is correct
11 Correct 14 ms 36696 KB Output is correct
12 Correct 12 ms 36696 KB Output is correct
13 Correct 21 ms 36692 KB Output is correct
14 Correct 21 ms 36700 KB Output is correct
15 Correct 23 ms 36700 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35184 KB Output is correct
4 Correct 9 ms 35188 KB Output is correct
5 Correct 7 ms 35164 KB Output is correct
6 Correct 8 ms 35248 KB Output is correct
7 Correct 9 ms 35164 KB Output is correct
8 Correct 7 ms 35164 KB Output is correct
9 Correct 8 ms 35164 KB Output is correct
10 Correct 17 ms 36700 KB Output is correct
11 Correct 14 ms 36696 KB Output is correct
12 Correct 12 ms 36696 KB Output is correct
13 Correct 21 ms 36692 KB Output is correct
14 Correct 21 ms 36700 KB Output is correct
15 Correct 23 ms 36700 KB Output is correct
16 Incorrect 534 ms 136360 KB Output isn't correct
17 Halted 0 ms 0 KB -