Submission #203969

#	Time	Username	Problem	Language	Result	Execution time	Memory
203969		tduong0806	Werewolf (IOI18_werewolf)	C++14	0 / 100	256 ms	31640 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=2010;

int n,m,q;

struct pack{
    int u,v,c;
};

struct kruskal{
    int dir, tim, it;
    vector<pack> edg;
    vector<int> ad[N];
    vector<int> id,st,ed,val,pos;
    vector<vector<int>> f;
    int root(int x){
        return id[x]==x? x : id[x]=root(id[x]);
    }
    void dfs(int u,int p=-1){
        st[u]=++tim; pos[tim]=u;
        forinc(i,1,20)
            f[u][i]=f[f[u][i-1]][i-1];
        forv(v,ad[u]) if(v!=p){
            f[v][0]=u;
            dfs(v,u);
        }
        ed[u]=tim;
    }
    ii que(int u,int x){
        if((dir && u>x) || (!dir && u<x)) return {n+n,n+n};
        if((dir && val[f[u][0]]>x) || (!dir && val[f[u][0]]<x)) return {st[u],ed[u]};
        u=f[u][0];
        fordec(i,20,0)
            if((dir && val[f[u][i]]<=x) || (!dir && val[f[u][i]]>=x)) u=f[u][i];
        return {st[u],ed[u]};
    }
    void build(int dire){ dir=dire;
        id.resize(N), st.resize(N), ed.resize(N), val.resize(N), f.resize(N), pos.resize(N);
        forv(i,f) i.resize(22);
        sort(all(edg),[](pack i,pack j){
            return i.c>j.c;
        });
        if(dir) reverse(all(edg));
        int it=n-1;
        forinc(i,1,n+n) id[i]=i;
        forv(i,edg){
            int u=i.u,
                v=i.v,
                c=i.c,
                x=root(u),
                y=root(v);
            if(x==y) continue;
            val[it+1]=c;
            ad[it+1].pb(x);
            ad[it+1].pb(y);
            id[x]=id[y]=++it;
        }
        dfs(f[it][0]=it);
    }
}pf,sf;

int T[N*4];
void upd(int s,int l,int r,int i){
    if(l>i||i>r) return;
    if(l==r){
        T[s]++;
        return;
    }
    int m=(l+r)/2;
    upd(2*s,l,m,i); upd(2*s+1,m+1,r,i);
    T[s]=T[2*s]+T[2*s+1];
}
int que(int s,int l,int r,int u,int v){
    if(l>v||u>r) return 0;
    if(u<=l&&r<=v)
        return T[s];
    int m=(l+r)/2;
    return que(2*s,l,m,u,v)+que(2*s+1,m+1,r,u,v);
}

vector<ii> qry[N];
ii range[N];

vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> st,vector<int> ed,vector<int> lf,vector<int> rt){
    m=x.size(), q=st.size();
    vector<int> ans(q);
    forinc(i,0,m-1){
        sf.edg.pb({x[i],y[i],max(x[i],y[i])});
        pf.edg.pb({x[i],y[i],min(x[i],y[i])});
    }
    sf.build(1);
    pf.build(0);
    forinc(i,0,q-1){
        ii u=pf.que(st[i],lf[i]);
        ii v=sf.que(ed[i],rt[i]);
        //cerr<<u.fi<<" "<<v.fi<<"\n";
        //cerr<<u.se<<" "<<v.se<<"\n";
        if(u.fi<n+n && v.fi<n+n){
            range[i]=v;
            qry[u.fi-1].pb({i,-1});
            qry[u.se].pb({i,1});
        }
    }
    forinc(i,1,n+n-1){
        if(pf.pos[i]<n) upd(1,0,n+n,sf.st[pf.pos[i]]);
        forv(j,qry[i]){
            //cerr<<range[j.fi].fi<<" "<<range[j.fi].se<<"\n";
            ans[j.fi]+=j.se * que(1,0,n+n,range[j.fi].fi,range[j.fi].se);
        }
    }
    forv(i,ans) i=!!i;
    return ans;
}
/**
main(){
    #define task "WEREWOLF"
    freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    vector<int> x,y,st,ed,lf,rt;
    cin>>n>>m>>q;
    forinc(i,1,m){
        x.pb(in),y.pb(in);
    }

    forinc(i,1,q){
        st.pb(in), ed.pb(in), lf.pb(in), rt.pb(in);
    }
    forv(i,check_validity(n,x,y,st,ed,lf,rt)) cout<<i<<"\n";
}
*/

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