Submission #610822

#	Time	Username	Problem	Language	Result	Execution time	Memory
610822		azberjibiou	Werewolf (IOI18_werewolf)	C++17	100 / 100	723 ms	80700 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
typedef struct qry{
    int s, e, l, r, idx;
}qry;
const int mxN=200200;
int N, M, Q;
qry A[mxN];
vector <pii> E;
vector <int> adj[mxN], adjr[mxN], adjl[mxN];
int inl[mxN], outl[mxN], inr[mxN], outr[mxN], invr[mxN];
int eidx;
vector <pii> cont[mxN];
vector <int> ans;
int par[mxN];
void init_uf(){for(int i=0;i<N;i++) par[i]=i;}
int findpar(int a){return (par[a]==a ? a : par[a]=findpar(par[a]));}
void onion(int a, int b, bool inv)
{
    int p=findpar(a), q=findpar(b);
    if(inv) par[max(p, q)]=min(p, q);
    else    par[min(p, q)]=max(p, q);
}
void dfsr(int now)
{
    inr[now]=eidx;
    for(int nxt : adjr[now])    dfsr(nxt);
    outr[now]=eidx++;
    invr[outr[now]]=now;
}
void dfsl(int now)
{
    inl[now]=eidx;
    for(int nxt : adjl[now])    dfsl(nxt);
    outl[now]=eidx++;
}
int seg[4*mxN];
void upd(int idx, int s, int e, int pos)
{
    if(s==e)
    {
        seg[idx]++;
        return;
    }
    int mid=(s+e)/2;
    if(pos<=mid)    upd(2*idx, s, mid, pos);
    else    upd(2*idx+1, mid+1, e, pos);
    seg[idx]++;
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s1>e2 || s2>e1)  return 0;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2);
}
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) {
    N=n;
    M=X.size();
    Q = S.size();
    ans.resize(Q);
    for(int i=0;i<Q;i++)
    {
        A[i].s=S[i], A[i].e=E[i], A[i].l=L[i], A[i].r=R[i], A[i].idx=i;
    }
    for(int i=0;i<M;i++)    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
    init_uf();
    sort(A, A+Q, [](qry a, qry b){return a.r<b.r;});
    int cur=0;
    for(int i=0;i<Q;i++)
    {
        while(cur<A[i].r)
        {
            for(int ele : adj[cur+1])   if(ele<=cur)    onion(ele, cur+1, false);
            cur++;
        }
        if(A[i].e>A[i].r)   A[i].e=-1;
        else    A[i].e=findpar(A[i].e);
    }
    init_uf();
    sort(A, A+Q, [](qry a, qry b){return a.l>b.l;});
    cur=N-1;
    for(int i=0;i<Q;i++)
    {
        while(cur>A[i].l)
        {
            for(int ele : adj[cur-1])   if(ele>=cur)    onion(ele, cur-1, true);
            cur--;
        }
        if(A[i].s<A[i].l)   A[i].s=-1;
        else    A[i].s=findpar(A[i].s);
    }
    sort(A, A+Q, [](qry a, qry b){return a.idx<b.idx;});
    init_uf();
    for(int i=1;i<N;i++)    for(int ele : adj[i])   if(ele<i && findpar(ele)!=i)
    {
        adjr[i].push_back(findpar(ele));
        onion(ele, i, false);
    }
    init_uf();
    for(int i=N-1;i>=0;i--) for(int ele : adj[i])   if(ele>i && findpar(ele)!=i)
    {
        adjl[i].push_back(findpar(ele));
        onion(ele, i, true);
    }
    eidx=1;
    dfsr(N-1);
    eidx=1;
    dfsl(0);
    for(int i=0;i<Q;i++)
    {
        if(A[i].s==-1 || A[i].e==-1)    continue;
        cont[inr[A[i].e]-1].emplace_back(i, -1);
        cont[outr[A[i].e]].emplace_back(i, 1);
    }
    for(int i=1;i<=N;i++)
    {
        int now=invr[i];
        upd(1, 1, N, outl[now]);
        for(pii ele : cont[i])
        {
            pii rng=pii(inl[A[ele.fir].s], outl[A[ele.fir].s]);
            ans[ele.fir]+=solv(1, 1, N, rng.fir, rng.sec)*ele.sec;
        }
    }
    for(int i=0;i<Q;i++)
    {
        if(A[i].s==-1 || A[i].e==-1)    ans[i]=0;
        else if(ans[i]!=0)  ans[i]=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
*/

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