oj.uz

Submission #789687

# Submission time Handle Problem Language Result Execution time Memory
789687 2023-07-21T19:01:06 Z benjaminkleyn Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 86600 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> g[200000];

int e[200000];
int par1[200000][20], par2[200000][20];
int find(int u)
{
    return e[u] == u ? u : e[u] = find(e[u]);
}

bool vis1[200000] = {false}, vis2[200000] = {false};
int euler1[200000], euler2[200000];
int in1[200000], out1[200000], t1 = 0;
int in2[200000], out2[200000], t2 = 0;
vector<int> c1[200000], c2[200000];
void dfs1(int u)
{
    vis1[u] = true;
    in1[u] = t1++;
    for (int v : c1[u])
        if (!vis1[v])
            dfs1(v);
    out1[u] = t1;
}
void dfs2(int u)
{
    vis2[u] = true;
    in2[u] = t2++;
    for (int v : c2[u])
        if (!vis2[v])
            dfs2(v);
    out2[u] = t2;
}

const int BS = 600;
struct Query
{
    int l1, r1, l2, r2, t;
};
bool operator<(const Query &A, const Query &B)
{
    return A.l1 / BS < B.l1 / BS || (A.l1 / BS == B.l1 / BS && A.r1 < B.r1);
}

int t[800000] = {0};
void update(int v, int tl, int tr, int idx, int val)
{
    if (idx < tl || tr < idx)
        return;
    if (tl == tr)
    {
        t[v] += val;
        return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, idx, val);
    update(2 * v + 1, tm + 1, tr, idx, val);
    t[v] = (t[2 * v] > 0) || (t[2 * v + 1] > 0);
}
int query(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l)
        return 0;
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) / 2;
    return (query(2 * v, tl, tm, l, r) > 0) || (query(2 * v + 1, tm + 1, tr, l, r) > 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 = S.size(), M = X.size();
    vector<int> A(Q, 0);

    for (int i = 0; i < N; i++)
        par1[i][0] = par2[i][0] = i;

    for (int i = 0; i < M; i++)
    {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < N; i++)
        e[i] = i;

    for (int u = 0; u < N; u++)
        for (int v : g[u])
            if (v < u)
            {
                v = find(v);
                e[v] = u;
                par1[v][0] = u;
            }

    for (int i = 0; i < N; i++)
        e[i] = i;

    for (int u = N - 1; u >= 0; u--)
        for (int v : g[u])
            if (v > u)
            {
                v = find(v);
                e[v] = u;
                par2[v][0] = u;
            }

    for (int k = 1; k < 20; k++)
        for (int u = 0; u < N; u++)
        {
            par1[u][k] = par1[par1[u][k-1]][k-1];
            par2[u][k] = par2[par2[u][k-1]][k-1];
        }

    for (int i = 0; i < N; i++)
    {
        c1[par1[i][0]].push_back(i);
        c2[par2[i][0]].push_back(i);
    }

    for (int i = N - 1; i >= 0; i--)
        if (!vis1[i])
            dfs1(i);

    for (int i = 0; i < N; i++)
        if (!vis2[i])
            dfs2(i);

    /*
    for (int i = 0; i < N; i++)
        cout << par1[i][0] << ' ';
    cout << '\n';

    for (int i = 0; i < N; i++)
        cout << par2[i][0] << ' ';
    cout << '\n';

    for (int i = 0; i < N; i++)
        cout << in1[i] << ' ';
    cout << '\n';

    for (int i = 0; i < N; i++)
        cout << in2[i] << ' ';
    cout << '\n';
    */

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++)
    {
        for (int k = 19; k >= 0; k--)
        {
            if (par1[E[i]][k] <= R[i])
                E[i] = par1[E[i]][k];
            if (par2[S[i]][k] >= L[i])
                S[i] = par2[S[i]][k];
        }
        queries[i] = {in1[E[i]], out1[E[i]]-1, in2[S[i]], out2[S[i]]-1, i};
    }

    for (int i = 0; i < N; i++)
    {
        euler1[in1[i]] = i;
        euler2[in2[i]] = i;
    }

    sort(queries.begin(), queries.end());
    int l = 0, r = -1;
    for (auto [l1, r1, l2, r2, t] : queries)
    {
        while (r < r1)
            update(1, 0, N - 1, in2[euler1[++r]], 1);
        while (l > l1)
            update(1, 0, N - 1, in2[euler1[--l]], 1);
        while (r > r1)
            update(1, 0, N - 1, in2[euler1[r--]], -1);
        while (l < l1)
            update(1, 0, N - 1, in2[euler1[l++]], -1);
        A[t] = query(1, 0, N - 1, l2, r2);
    }

    return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14404 KB Output is correct
6 Correct 7 ms 14404 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14404 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14404 KB Output is correct
6 Correct 7 ms 14404 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14404 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct
10 Correct 47 ms 15572 KB Output is correct
11 Correct 38 ms 15540 KB Output is correct
12 Correct 17 ms 15572 KB Output is correct
13 Correct 79 ms 15728 KB Output is correct
14 Correct 66 ms 15720 KB Output is correct
15 Correct 24 ms 15700 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 82952 KB Output is correct
2 Correct 1264 ms 86600 KB Output is correct
3 Correct 3550 ms 84280 KB Output is correct
4 Execution timed out 4082 ms 83308 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14404 KB Output is correct
6 Correct 7 ms 14404 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14404 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct
10 Correct 47 ms 15572 KB Output is correct
11 Correct 38 ms 15540 KB Output is correct
12 Correct 17 ms 15572 KB Output is correct
13 Correct 79 ms 15728 KB Output is correct
14 Correct 66 ms 15720 KB Output is correct
15 Correct 24 ms 15700 KB Output is correct
16 Correct 1440 ms 82952 KB Output is correct
17 Correct 1264 ms 86600 KB Output is correct
18 Correct 3550 ms 84280 KB Output is correct
19 Execution timed out 4082 ms 83308 KB Time limit exceeded
20 Halted 0 ms 0 KB -