oj.uz

Submission #254154

# Submission time Handle Problem Language Result Execution time Memory
254154 2020-07-29T12:12:22 Z davitmarg Werewolf (IOI18_werewolf) C++17
100 / 100
 2325 ms 230264 KB 
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)


#ifndef death
#include "werewolf.h"
#endif

using namespace std;

const int N = 200005;

int parent[N], sz[N], P[N], id[N + N];
int timer, tin[N + N], tout[N + N], up[N + N][30], mx[N + N][30];
int m,k;
vector<int> G[N + N];

void init(int n,int x=0)
{
    m = n;
    timer = 0;
    for (int i = 1; i <= n; i++)
    {
        G[i].clear();
        id[i] = x;
        G[i+n].clear();
        tin[i] = tin[i + n] = 0;
        P[i] = i;
        parent[i] = i;
        sz[i] = 1;
    }
}

int getPar(int v)
{
    if (parent[v] == v)
        return v;
    return parent[v] = getPar(parent[v]);
}

void dsu(int a, int b,int val)
{
    a = getPar(a);
    b = getPar(b);
    if (a == b)
        return;
    if (sz[a] < sz[b])
        swap(a, b);
    m++;
    G[m].push_back(P[a]);
    G[m].push_back(P[b]);
    parent[b] = a;
    sz[a] += sz[b];
    P[a] = m;
    id[m] = val;
}

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    mx[v][0] = max(id[p], id[v]);

    for (int i = 1; i <= k; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
    }

    for (int i = 0; i < G[v].size(); i++)
    {
        int to = G[v][i];
        //cout << v << " : " << to << endl;
        dfs(to, v);
    }
    tout[v] = timer;
}

int n,x[N],y[N],q;
vector<int> g[N];
pair<int, int> s[N],e[N];

vector<int> t[8 * N];

void add(int v, int l, int r,int pos,int val)
{
    t[v].push_back(val);
    if (l == r)
        return;
    int m = (l + r) / 2;
    if (pos <= m)
        add(v * 2, l, m, pos, val);
    else
        add(v * 2 + 1, m + 1, r, pos, val);
}

void build(int v, int l, int r)
{
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    sort(all(t[v]));
}

bool get(int v, int l, int r, int i, int j, int L, int R)
{
    if (i > j)
        return 0;
    if (l == i && r == j)
    {
        if (t[v].empty())
            return 0;
        if (t[v][0] > R || t[v].back() < L)
            return 0;
        return (*lower_bound(all(t[v]), L) <= R);
    }
    int m = (l + r) / 2;
    return (
        get(v * 2, l, m, i, min(m, j), L, R) |
        get(v * 2 + 1, m + 1, r, max(m + 1, i), j, L, R));
}

vector<int> ans;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>L, vector<int> R)
{
    n = N;
    q = S.size();
    for (int i = 0; i < X.size();i++)
    {
        g[X[i] + 1].push_back(Y[i] + 1);
        g[Y[i] + 1].push_back(X[i] + 1);
    }

    //E
    init(n);
    for (int v = 1; v <= n; v++)
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (to > v)
                continue;
            dsu(v, to, v);
        }
    k = 0;
    while ((1 << k) <= m)
        k++;

    for (int i = 1; i <= n; i++)
    {
        int v = P[getPar(i)];
        if (!tin[v])
            dfs(v, v);
    }

    for (int v = 1; v <= n; v++)
        x[v] = tin[v];
    
    for (int i = 0; i < E.size(); i++)
    {
        E[i]++;
        R[i]++;
        int v = E[i];
        for (int j = k; j >= 0; j--)
            if (mx[v][j] <= R[i])
                v = up[v][j];
        e[i + 1] = MP(tin[v], tout[v]);
    }

    //S

    init(n, -n - 1);
    for (int v = n; v >= 1; v--)
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (to < v)
                continue;
            dsu(v, to, -v);
        }

    k = 0;
    while ((1 << k) <= m)
        k++;

    for (int i = 1; i <= n; i++)
    {
        int v = P[getPar(i)];
        if (!tin[v])
            dfs(v, v);
    }

    for (int v = 1; v <= n; v++)
        y[v] = tin[v];

    for (int i = 0; i < S.size(); i++)
    {
        S[i]++;
        L[i]++;
        int v = S[i];
        for (int j = k; j >= 0; j--)
            if (mx[v][j] <= -L[i])
                v = up[v][j];
        s[i + 1] = MP(tin[v], tout[v]);
    }

    for (int i = 1; i <= n; i++)
        add(1, 1, n + n,y[i], x[i]);

    build(1, 1, n + n);

    for (int i = 1; i <= q; i++)
        ans.push_back(get(1, 1, n + n, s[i].first, s[i].second, e[i].first, e[i].second));
    return ans;
}

#ifdef death
int main()
{
    fastIO;
    int n, m, q;
    vector<int> X, Y, L, R, S, E;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        X.PB(a);
        Y.PB(b);
    }

    for (int i = 0; i < q; i++)
    {
        int a, b,l,r;
        cin >> a >> b >> l >> r;
        S.PB(a);
        E.PB(b);
        L.PB(l);
        R.PB(r);
    }

    vector<int> ANS = check_validity(n, X, Y, S, E, L, R);
    for (int i = 0; i < ANS.size(); i++)
        cout << ANS[i] << endl;
    return 0;
}

#endif

/*




*/

Compilation message

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < G[v].size(); i++)
                     ~~^~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size();i++)
                     ~~^~~~~~~~~~
werewolf.cpp:167:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~
werewolf.cpp:188:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < E.size(); i++)
                     ~~^~~~~~~~~~
werewolf.cpp:203:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~
werewolf.cpp:225:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); i++)
                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52096 KB Output is correct
2 Correct 32 ms 52088 KB Output is correct
3 Correct 35 ms 52096 KB Output is correct
4 Correct 29 ms 52088 KB Output is correct
5 Correct 33 ms 52072 KB Output is correct
6 Correct 29 ms 52088 KB Output is correct
7 Correct 30 ms 52096 KB Output is correct
8 Correct 29 ms 52096 KB Output is correct
9 Correct 29 ms 52180 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52096 KB Output is correct
2 Correct 32 ms 52088 KB Output is correct
3 Correct 35 ms 52096 KB Output is correct
4 Correct 29 ms 52088 KB Output is correct
5 Correct 33 ms 52072 KB Output is correct
6 Correct 29 ms 52088 KB Output is correct
7 Correct 30 ms 52096 KB Output is correct
8 Correct 29 ms 52096 KB Output is correct
9 Correct 29 ms 52180 KB Output is correct
10 Correct 47 ms 54392 KB Output is correct
11 Correct 40 ms 54400 KB Output is correct
12 Correct 40 ms 54528 KB Output is correct
13 Correct 45 ms 54520 KB Output is correct
14 Correct 41 ms 54520 KB Output is correct
15 Correct 49 ms 54520 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1963 ms 211552 KB Output is correct
2 Correct 1692 ms 223972 KB Output is correct
3 Correct 1597 ms 221536 KB Output is correct
4 Correct 1522 ms 220132 KB Output is correct
5 Correct 1591 ms 220060 KB Output is correct
6 Correct 1852 ms 219868 KB Output is correct
7 Correct 1714 ms 220008 KB Output is correct
8 Correct 1634 ms 223840 KB Output is correct
9 Correct 1269 ms 221540 KB Output is correct
10 Correct 1182 ms 220132 KB Output is correct
11 Correct 1192 ms 220056 KB Output is correct
12 Correct 1364 ms 219856 KB Output is correct
13 Correct 1642 ms 222264 KB Output is correct
14 Correct 1628 ms 222108 KB Output is correct
15 Correct 2008 ms 222172 KB Output is correct
16 Correct 2088 ms 222180 KB Output is correct
17 Correct 1725 ms 220128 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52096 KB Output is correct
2 Correct 32 ms 52088 KB Output is correct
3 Correct 35 ms 52096 KB Output is correct
4 Correct 29 ms 52088 KB Output is correct
5 Correct 33 ms 52072 KB Output is correct
6 Correct 29 ms 52088 KB Output is correct
7 Correct 30 ms 52096 KB Output is correct
8 Correct 29 ms 52096 KB Output is correct
9 Correct 29 ms 52180 KB Output is correct
10 Correct 47 ms 54392 KB Output is correct
11 Correct 40 ms 54400 KB Output is correct
12 Correct 40 ms 54528 KB Output is correct
13 Correct 45 ms 54520 KB Output is correct
14 Correct 41 ms 54520 KB Output is correct
15 Correct 49 ms 54520 KB Output is correct
16 Correct 1963 ms 211552 KB Output is correct
17 Correct 1692 ms 223972 KB Output is correct
18 Correct 1597 ms 221536 KB Output is correct
19 Correct 1522 ms 220132 KB Output is correct
20 Correct 1591 ms 220060 KB Output is correct
21 Correct 1852 ms 219868 KB Output is correct
22 Correct 1714 ms 220008 KB Output is correct
23 Correct 1634 ms 223840 KB Output is correct
24 Correct 1269 ms 221540 KB Output is correct
25 Correct 1182 ms 220132 KB Output is correct
26 Correct 1192 ms 220056 KB Output is correct
27 Correct 1364 ms 219856 KB Output is correct
28 Correct 1642 ms 222264 KB Output is correct
29 Correct 1628 ms 222108 KB Output is correct
30 Correct 2008 ms 222172 KB Output is correct
31 Correct 2088 ms 222180 KB Output is correct
32 Correct 1725 ms 220128 KB Output is correct
33 Correct 1696 ms 220512 KB Output is correct
34 Correct 486 ms 88184 KB Output is correct
35 Correct 2325 ms 224752 KB Output is correct
36 Correct 1715 ms 220248 KB Output is correct
37 Correct 1751 ms 223220 KB Output is correct
38 Correct 1891 ms 220848 KB Output is correct
39 Correct 1486 ms 229680 KB Output is correct
40 Correct 2116 ms 228980 KB Output is correct
41 Correct 1577 ms 222180 KB Output is correct
42 Correct 1472 ms 220388 KB Output is correct
43 Correct 1839 ms 228184 KB Output is correct
44 Correct 1648 ms 223196 KB Output is correct
45 Correct 1372 ms 229484 KB Output is correct
46 Correct 1328 ms 229544 KB Output is correct
47 Correct 1874 ms 222432 KB Output is correct
48 Correct 2153 ms 222040 KB Output is correct
49 Correct 1647 ms 222384 KB Output is correct
50 Correct 1621 ms 222180 KB Output is correct
51 Correct 1542 ms 229976 KB Output is correct
52 Correct 1550 ms 230264 KB Output is correct