Submission #400658

#	Time	Username	Problem	Language	Result	Execution time	Memory
400658		iulia13	Werewolf (IOI18_werewolf)	C++14	49 / 100	4096 ms	116892 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define pb push_back
const int MAX_N = 4e5 + 5;
const int MAX_LOG = 20;
vector <int> g[MAX_N];
vector <int> T1[MAX_N];
vector <int> T2[MAX_N];
int dad1[MAX_N][MAX_LOG], dad2[MAX_N][MAX_LOG];
int set1[MAX_N], set2[MAX_N];
int S(int x, int SET[])
{
    if (x != SET[x])
        return x = S(SET[x], SET);
    else
        return x;
}
void unire(int x, int y, int SET[], int dad[MAX_N][MAX_LOG])
{
    int xx = S(x, SET);
    int yy = S(y, SET);
    if (xx == yy)
        return;
    dad[yy][0] = x;
    SET[yy] = x;
}
void arb(int dad[MAX_N][MAX_LOG], int n, vector <int> T[])
{
    for (int i = 1; i <= n; i++)
    {
        T[i].pb(dad[i][0]);
        T[dad[i][0]].pb(i);
    }
}
int timp;
int in1[MAX_N], out1[MAX_N], in2[MAX_N], out2[MAX_N];
int intime[MAX_N], outtime[MAX_N];
void dfs1(int nod, int dad = 0)
{
    in1[nod] = ++timp;
    for (auto x : T1[nod])
    {
        if (x == dad || !x)
            continue;
        dfs1(x, nod);
    }
    out1[nod] = timp;
}


int aib[MAX_N * 2];
int N;
int lsb(int x)
{
    return x & (-x);
}
int query(int pz)
{
    int s = 0;
    while (pz > 0)
    {
        s += aib[pz];
        pz -= lsb(pz);
    }
    return s;
}
void update(int pz, int val)
{
    while (pz <= N)
    {
        aib[pz] += val;
        pz += lsb(pz);
    }
}
void dfs2(int nod, int dad = 0)
{
    in2[nod] = ++timp;
    intime[timp] = nod;
    for (auto x : T2[nod])
    {
        if (x == dad || !x)
            continue;
        dfs2(x, nod);
    }
    out2[nod] = timp;
}
struct Interval{
    int x, l, r, tip, ind;
};
bool cmp(Interval a, Interval b)
{
    return a.x < b.x;
}
Interval interv[MAX_N];
vector <int> A;
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 i; N = n;
    for (i = 0; i < X.size(); i++)
    {
        g[X[i] + 1].pb(Y[i] + 1);
        g[Y[i] + 1].pb(X[i] + 1);
    }
    for (i = 1; i <= n; i++)
        set1[i] = set2[i] = i;
    ///pt l <=
    for (i = 1; i <= n; i++)
        for (auto x : g[i])
            if (x < i)
                unire(i, x, set1, dad1);

    arb(dad1, n, T1);

    timp = 0;
    dfs1(n);

    ///pt  <= r
    for (i = n; i; i--)
        for (auto x : g[i])
            if (i < x)
                unire(i, x, set2, dad2);

    arb(dad2, n, T2);

    timp = 0;
    dfs2(1);

    ///LIFT
    for (int j = 1; j < MAX_LOG; j++)
        for (i = 1; i <= n; i++)
        {
            dad1[i][j] = dad1[dad1[i][j - 1]][j - 1];
            dad2[i][j] = dad2[dad2[i][j - 1]][j - 1];
        }
int    cnt = 0;
    for (i = 0; i < S.size(); i++)
    {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        s++, e++, l++, r++;
        int lg = MAX_LOG - 1;
        while (0 <= lg)
        {
            if (l <= dad2[s][lg])
                s = dad2[s][lg];
            lg--;
        }
        lg = MAX_LOG - 1;
        while (0 <= lg)
        {
            if (dad1[e][lg] && dad1[e][lg] <= r)
                e = dad1[e][lg];
            lg--;
        }
        interv[++cnt] = {in2[s] - 1, in1[e], out1[e], -1, i};
        interv[++cnt] = {out2[s], in1[e], out1[e], 1, i};
    }
    sort(interv + 1, interv + cnt + 1, cmp);
    A.resize(S.size());
    int j = 1;
    for (i = 1; i <= cnt; i++)
    {
        while (j <= interv[i].x)
        {
            update(in1[intime[j]], 1);
            j++;
        }
        A[interv[i].ind] += interv[i].tip * (query(interv[i].r) - query(interv[i].l - 1));
    }
    for (i = 0; i < A.size(); i++)
        if (A[i] > 0)
            A[i] = 1;
        else
            A[i] = 0;
    return A;
}/*
vector <int> x;
vector <int> y;
vector <int> s;
vector <int> e;
vector <int> l;
vector <int> r;
int main()
{
    int n,  m, q, i;
    cin >> n >> m >> q;
    x.resize(m);
    y.resize(m);
    for (i = 0; i < m; i++)
        cin >> x[i];
    for (i = 0; i < m; i++)
        cin >> y[i];
    s.resize(q);
    e.resize(q);
    l.resize(q);
    r.resize(q);
    for (i = 0; i < q; i++)
        cin >> s[i];
    for (i = 0; i < q; i++)
        cin >> e[i];
    for (i = 0; i < q; i++)
        cin >> l[i];
    for (i = 0; i < q; i++)
        cin >> r[i];
    vector <int> aaa = check_validity(n, x, y, s, e, l, r);
    aaa.resize(q);
    for(i = 0; i < q; i++)
        cout << aaa[i];
    return 0;
}*/

Compilation message (stderr)

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:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (i = 0; i < X.size(); i++)
      |                 ~~^~~~~~~~~~
werewolf.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (i = 0; i < S.size(); i++)
      |                 ~~^~~~~~~~~~
werewolf.cpp:173:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (i = 0; i < A.size(); i++)
      |                 ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51