Submission #1148886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148886		modwwe	Werewolf (IOI18_werewolf)	C++20	100 / 100	927 ms	95124 KiB

werewolf

//#include "combo.h"
//#include "one.h"
//#include "werewolf.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9+7;
const ll base=67;
int  n,m,s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,last;
int kk;
int el = 19;
struct ic
{
    int a,b,c;
};
struct ib
{
    int a, b;
};
struct id
{
    int a,b,c,d;
};
int t[1600001], ain[400001], aou[400001], bin[400001], bou[400001], st[19][400001];
vector<int> v[400001],ans;
vector<id> ask[400001];
int cost[400001], pos[400001];
vector<ib>edge;
struct dsuconcu
{
    ic dsu[200001];
    void reset()
    {
        for(int i=1; i<=n; i++)
            dsu[i]= {1,i,i};
        for(int i=1; i<=dem; i++)
            v[i].clear();
        dem=n;
    }
    int get(int x)
    {
        if(x!=dsu[x].b) dsu[x].b=get(dsu[x].b);
        return dsu[x].b;
    }
    void noi(int x,int y,int xx)
    {
        x=get(x);
        y=get(y);
        if(x==y) return;
        if(dsu[x].a<dsu[y].a)swap(x,y);
        dsu[x].a+=dsu[y].a;
        dsu[y].b=x;
        dem++;
        cost[dem]=xx;
        /// cout<<x<<" "<<y<<" "<<xx,debug
        v[dem].pb(dsu[x].c);
        v[dem].pb(dsu[y].c);
        dsu[x].c=dem;
    }
} dsu;
void upd(int node,int l,int r,int l1,int x)
{
    if(l>l1||r<l1) return;
    if(l==r)
    {
        t[node]=x;
        return;
    }
    int mid=l+r>>1;
    upd(node<<1,l,mid,l1,x);
    upd(node<<1|1,mid+1,r,l1,x);
    t[node]=max(t[node<<1],t[node<<1|1]);
}
int get(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1){
            return t[node];}
    int mid=l+r>>1;
    return max(get(node << 1, l, mid, l1, r1 ),get(node << 1 | 1,mid + 1, r, l1, r1));
}
void dfs(int x,bool d)
{
    if(!d)ain[x]=++dem2,pos[dem2]=x;
    else bin[x]=++dem2;
    for(auto f:v[x])
    {
       st[0][f]=x;
        dfs(f,d);
    }
    if(!d)aou[x]=dem2;
    else bou[x]=dem2;
}
void build(int xx)
{
    dsu.reset();
    for(int i=0; i<m; i++)
    {
        int x=edge[i].a+1;
        int y=edge[i].b+1;
        if(xx==0)dsu.noi(x,y,max(x,y));
        else dsu.noi(x,y,min(x,y));
    }
    cost[0]=inf;
    dfs(dem,xx);
    for(int i=1; i<19; i++)
        for(int j=1; j<=dem; j++)
            st[i][j]=st[i-1][st[i-1][j]];
}
bool cmp(ib a,ib b)
{
    return max(a.a,a.b)<max(b.a,b.b);
}
bool cmp2(ib a,ib b)
{
    return min(a.a,a.b)>min(b.a,b.b);
}
vector<int> check_validity(int N,vector<int>X,vector<int>Y,vector<int> start,
                           vector<int> target,vector<int>L,vector<int>R)
{
    n=N;
    m=X.size();
    for(int i=0; i<X.size(); i++)
    {
        edge.pb({X[i],Y[i]});
    }
    sort(edge.begin(),edge.end(),cmp);
    build(0);
    int q=start.size();
    ans.resize(q);
    for(int i=0; i<q; i++)
    {
        int x=target[i]+1;
        for(int j=18; j>=0; --j)
            if(cost[st[j][x]]<=R[i]+1)
                x=st[j][x];
        target[i]=x;
    }
    sort(edge.begin(),edge.end(),cmp2);
    dem2=0;
    build(1);
    cost[0]=-inf;
    for(int i=0; i<q; i++)
    {
        int x=start[i]+1;
        for(int j=18; j>=0; --j)
            if(cost[st[j][x]]>=L[i]+1)
                x=st[j][x];
        ask[aou[target[i]]].pb({ain[target[i]],bin[x],bou[x],i});
    }
    for(int i=1; i<=2*n; i++)
    {
        if(pos[i]<=n)
            upd(1,1,2*n,bin[pos[i]],i);
        for(auto x:ask[i])
        {
            s2=get(1,1,n*2,x.b,x.c);
            if(s2>=x.a)ans[x.d]=1;
        }
    }
    return ans;
}
/*
int main(){
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N, M, Q; cin >> N >> M >> Q;
    vector <int> X(M), Y(M);
    for (int i = 0; i < M; ++ i)
        cin >> X[i] >> Y[i];

    vector <int> S(Q), E(Q), L(Q), R(Q);
    for (int i = 0; i < Q; ++ i)
        cin >> S[i] >> E[i] >> L[i] >> R[i];

    vector <int> ans = check_validity(N, X, Y, S, E, L, R);
    for (int A : ans)
        cout << A << "\n";

    return 0;
}
*/

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