oj.uz

Submission #938958

# Submission time Handle Problem Language Result Execution time Memory
938958 2024-03-06T01:37:22 Z LOLOLO Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 127876 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], pos[N], L[N], R[N], val[N * 2];
int 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 9 ms 33372 KB Output is correct
2 Correct 9 ms 33372 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 10 ms 33116 KB Output is correct
5 Correct 7 ms 33112 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 9 ms 33372 KB Output is correct
9 Correct 7 ms 33624 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33372 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 10 ms 33116 KB Output is correct
5 Correct 7 ms 33112 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 9 ms 33372 KB Output is correct
9 Correct 7 ms 33624 KB Output is correct
10 Correct 17 ms 34652 KB Output is correct
11 Correct 14 ms 34652 KB Output is correct
12 Correct 12 ms 34648 KB Output is correct
13 Correct 22 ms 34652 KB Output is correct
14 Correct 21 ms 34744 KB Output is correct
15 Correct 20 ms 34908 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 127876 KB Output is correct
2 Execution timed out 4037 ms 93740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 9 ms 33372 KB Output is correct
3 Correct 7 ms 33116 KB Output is correct
4 Correct 10 ms 33116 KB Output is correct
5 Correct 7 ms 33112 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 9 ms 33372 KB Output is correct
9 Correct 7 ms 33624 KB Output is correct
10 Correct 17 ms 34652 KB Output is correct
11 Correct 14 ms 34652 KB Output is correct
12 Correct 12 ms 34648 KB Output is correct
13 Correct 22 ms 34652 KB Output is correct
14 Correct 21 ms 34744 KB Output is correct
15 Correct 20 ms 34908 KB Output is correct
16 Correct 486 ms 127876 KB Output is correct
17 Execution timed out 4037 ms 93740 KB Time limit exceeded
18 Halted 0 ms 0 KB -