Submission #431932

#	Time	Username	Problem	Language	Result	Execution time	Memory
431932		Enkognit	Werewolf (IOI18_werewolf)	C++14	100 / 100	1543 ms	158772 KiB

werewolf

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#include "werewolf.h"

using namespace std;

ll N;
vector<ll> c[200005], g1[200005], g2[200005];
ll in1[200005], out1[200005], in2[200005], out2[200005];
ll bn1[200005][20], bn2[200005][20];
vector<ll> v1, v2;

void dfs1(int h,int p)
{
    bn1[h][0]=p;
    for (int i = 1; i < 20; i++)
        if (bn1[h][i-1]!=N) bn1[h][i]=bn1[bn1[h][i-1]][i-1]; else bn1[h][i]=N;

    in1[h]=v1.size();

    v1.pb(h);

    for (int i = 0; i < g1[h].size(); i++)
        dfs1(g1[h][i], h);

    out1[h]=v1.size();

    v1.pb(h);
}

void dfs2(int h,int p=-1)
{
    bn2[h][0]=p;
    for (int i = 1; i < 20; i++)
        if (bn2[h][i-1]!=-1)bn2[h][i]=bn2[bn2[h][i-1]][i-1]; else bn2[h][i]=-1;

    in2[h]=v2.size();

    v2.pb(h);

    for (int i = 0; i < g2[h].size(); i++)
        dfs2(g2[h][i], h);

    out2[h]=v2.size();

    v2.pb(h);
}

    ll d[1600001];

    void build(int h,int l,int r)
    {
        if (l==r)
        {
            d[h]=-1;
            return;
        }
        int w=(l+r)/2;
        build(h*2,l,w);
        build(h*2+1,w+1,r);
        d[h]=max(d[h*2], d[h*2+1]);
    }

    ll get(int h,int l,int r,int x,int y)
    {
        if (x>y) return -1;
        if (l==x && y==r) return d[h];
        int w=(l+r)/2;
        return max(get(h*2,l,w,x,min(y,w)), get(h*2+1,w+1,r,max(x,w+1),y));
    }

    void update(int h,int l,int r,int x,int k)
    {
        if (l==r)
        {
            d[h]=k;
            return;
        }
        int w=(l+r)/2;
        if (x<=w) update(h*2,l,w,x,k); else update(h*2+1,w+1,r,x,k);
        d[h]=max(d[h*2], d[h*2+1]);
    }


struct dsu
{
    ll d[1000001];

    void make_sets(int h)
    {
        for (int i = 0; i <= h; i++)
            d[i]=i;
    }

    ll find_set(int h)
    {
        if (h==d[h]) return h; else return d[h]=find_set(d[h]);
    }

    bool unite_sets(int x,int y)
    {
        x=find_set(x);
        y=find_set(y);
        if (x!=y)
        {
            d[y]=x;
            return 1;
        }
        return 0;
    }
} gg;


std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> l, std::vector<int> r) {
    for (int i = 0; i < x.size(); i++)
    {
        c[x[i]].pb(y[i]);
        c[y[i]].pb(x[i]);
    }

    N=n;

    vector<int> ans;
    ans.resize(s.size());

    gg.make_sets(n);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < c[i].size(); j++)
            if (c[i][j]<i)
            {
                ll to=gg.find_set(c[i][j]);
                if (gg.unite_sets(i, to))
                {
                    g1[i].pb(to);
                    //cout << " " << i << " " << to << "\n";
                }
            }
    }

    gg.make_sets(n);

    for (int i = n-1; i > -1; i--)
    {
        for (int j = 0; j < c[i].size(); j++)
            if (c[i][j]>i)
            {
                ll to=gg.find_set(c[i][j]);
                if (gg.unite_sets(i, to))
                {
                    g2[i].pb(to);
                    //cout << i << " " << to << "\n";
                }
            }
    }

    dfs1(n-1, n);
    dfs2(0, -1);

    ll m=s.size();

    vector<pair<pair<pll, pll>, ll> > zp;

    for (int i = 0; i < m; i++)
    {
        ll x, y;

        x=s[i];

        for (int j = 19; j > -1; j--)
            if (bn2[x][j]>=l[i]) x=bn2[x][j];

        y=e[i];

        for (int j = 19; j > -1; j--)
            if (bn1[y][j]<=r[i]) y=bn1[y][j];

        //cout << x << " " << y << " " << e[i] << "\n";

        zp.pb(mp(mp(mp(out2[x], in2[x]), mp(in1[y], out1[y])), i));
    }

    sort(all(zp));

    ll lr=-1;

    for (int i = 0; i < v2.size(); i++)
    {
        update(1,0,v1.size()-1,in1[v2[i]], i);
        update(1,0,v1.size()-1,out1[v2[i]], i);
        while (lr+1<zp.size() && i==zp[lr+1].fi.fi.fi)
        {
            lr++;
            if (get(1, 0, v1.size()-1, zp[lr].fi.se.fi, zp[lr].fi.se.se)>=zp[lr].fi.fi.se) ans[zp[lr].se]=1;
        }
    }

    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < g1[h].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < g2[h].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:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int j = 0; j < c[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:155:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (int j = 0; j < c[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for (int i = 0; i < v2.size(); i++)
      |                     ~~^~~~~~~~~~~
werewolf.cpp:201:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> >, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         while (lr+1<zp.size() && i==zp[lr+1].fi.fi.fi)
      |                ~~~~^~~~~~~~~~

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