Submission #556098

#	Time	Username	Problem	Language	Result	Execution time	Memory
556098		n0sk1ll	Werewolf (IOI18_werewolf)	C++14	100 / 100	892 ms	118732 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

vector<vector<int>> manji(200005),veci(200005);

int up[200005];
vector<int> redosled[200005];
int poc[200005],kraj[200005];
int gde[200005];

int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b);
    if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
    for (auto it : redosled[a]) redosled[b].pb(it);
}

vector<pii> pom[200005];

int niz1[200005];
int l1[200005],r1[200005];

int niz2[200005];
int l2[200005],r2[200005];

int gdeu1[200005];

int k=1;
vector<int> val[550001];
int l[550001],r[550001];

int Qry(int p, int ll, int rr, int x)
{
    if (ll>r[p] || rr<l[p]) return 0;
    if (ll<=l[p] && rr>=r[p]) return lower_bound(all(val[p]),x)-val[p].begin();
    return Qry(2*p,ll,rr,x)+Qry(2*p+1,ll,rr,x);
}

void ispisi()
{
    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk)
        {
            for (auto it : val[i]) cout<<it<<" ";
            cout<<"; ";
        } cout<<endl;
    } cout<<endl;
}

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=X.size();
    int q=S.size();
    vector<int> ans(q,0);

    ff(i,0,m)
    {
        if (X[i]>Y[i]) swap(X[i],Y[i]);
        manji[Y[i]].pb(X[i]),veci[X[i]].pb(Y[i]);
    }

    ///wolf form

    ff(i,0,q) pom[i].clear();
    ff(i,0,q) pom[R[i]].pb({E[i],i});

    ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);

    ff(i,0,n)
    {
        for (auto it : manji[i]) dsu(i,it);
        for (auto it : pom[i])
        {
            poc[it.yy]=redosled[Up(it.xx)].front();
            kraj[it.yy]=redosled[Up(it.xx)].back();
        }
    }
    ff(i,0,n) niz1[i]=redosled[Up(0)][i];
    ff(i,0,n) gde[niz1[i]]=i;
    ff(i,0,q) l1[i]=gde[poc[i]],r1[i]=gde[kraj[i]];

    //ff(i,0,n) cout<<niz1[i]<<" "; cout<<endl;
    //ff(i,0,q) cout<<"["<<l1[i]<<","<<r1[i]<<"]"<<endl; cout<<endl;

    ///human form

    ff(i,0,q) pom[i].clear();
    ff(i,0,q) pom[L[i]].pb({S[i],i});

    ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);

    bff(i,0,n)
    {
        for (auto it : veci[i]) dsu(i,it);
        for (auto it : pom[i])
        {
            poc[it.yy]=redosled[Up(it.xx)].front();
            kraj[it.yy]=redosled[Up(it.xx)].back();
        }
    }
    ff(i,0,n) niz2[i]=redosled[Up(0)][i];
    ff(i,0,n) gde[niz2[i]]=i;
    ff(i,0,q) l2[i]=gde[poc[i]],r2[i]=gde[kraj[i]];

    //ff(i,0,n) cout<<niz2[i]<<" "; cout<<endl;
    //ff(i,0,q) cout<<"["<<l2[i]<<","<<r2[i]<<"]"<<endl; cout<<endl;

    ///intersect?

    ff(i,0,n) gdeu1[niz1[i]]=i;
    while (k<n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,0,n) val[i+k].pb(gdeu1[niz2[i]]);
    bff(i,1,k) val[i].resize(val[2*i].size()+val[2*i+1].size()),merge(all(val[2*i]),all(val[2*i+1]),val[i].begin());

    ff(i,0,q)
    {
        if (Qry(1,l2[i],r2[i],r1[i]+1)!=Qry(1,l2[i],r2[i],l1[i])) ans[i]=1;
    }

    return ans;
}

/*

6 6 3
5 1
1 2
1 3
3 4
0 3
2 5
4 2 1 2
4 2 2 2
5 4 3 4

6 6 21
5 1
1 2
1 3
3 4
0 3
2 5
0 0 0 0
0 0 1 1
0 0 2 2
0 0 3 3
0 0 4 4
0 0 5 5
1 1 1 1
1 1 2 2
1 1 3 3
1 1 4 4
1 1 5 5
2 2 2 2
2 2 3 3
2 2 4 4
2 2 5 5
3 3 3 3
3 3 4 4
3 3 5 5
4 4 4 4
4 4 5 5
5 5 5 5

*/

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