Submission #1217402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217402		mariza	Werewolf (IOI18_werewolf)	C++20	0 / 100	266 ms	43848 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MID ((l+r)/2)
const ll N=2e5;

vector<ll> g[N];
ll c=0, idx[N], a[N];
void dfs(ll curr, ll prev){
    a[c]=curr;
    idx[curr]=c;
    c++;

    for(auto nxt:g[curr]){
        if(nxt!=prev) dfs(nxt,curr);
    }
}

struct query{
    ll s, e, l, r, idx;
    ll hl, hr, wl, wr;
};

bool comp_l(query a, query b){
    return a.l>b.l;
}

bool comp_r(query a, query b){
    return a.r<b.r;
}

bool comp_i(query a, query b){
    return a.idx<b.idx;
}

struct DSU{
    ll p[N];
    ll l[N], r[N];

    void init(ll n){
        for(ll i=0; i<n; i++){
            p[i]=i;
            l[i]=i;
            r[i]=i;
        }
    }

    ll find(ll u){
        if(p[u]==u) return u;
        else return p[u]=find(p[u]);
    }

    void merge(ll u, ll v){
        u=find(u);
        v=find(v);

        l[u]=min(l[u],l[v]);
        r[u]=max(r[u],r[v]);
        p[v]=u;
    }
};

vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> qs, vector<int> qe, vector<int> ql, vector<int> qr) {
    for(ll i=0; i<u.size(); i++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    for(ll i=0; i<n; i++){
        if(g[i].size()==1){
            dfs(i,i);
            break;
        }
    }

    // for(ll i=0; i<n; i++){
    //     cout<<a[i]<<" ";
    // }
    // cout<<endl;

    query q[qs.size()];
    for(ll i=0; i<qs.size(); i++){
        q[i]={qs[i],qe[i],ql[i],qr[i],i};
    }

    DSU dsu;
    dsu.init(n);
    sort(q,q+qs.size(),comp_l);
    ll l=n;
    for(auto &curr:q){
        // cout<<idx[curr.s]<<endl;
        while(curr.l<l){
            l--;
            if(0<idx[l] && a[idx[l]-1]>=l) dsu.merge(idx[l],idx[l]-1);
            if(idx[l]<n-1 && a[idx[l]+1]>=l) dsu.merge(idx[l],idx[l]+1);
        }

        // cout<<curr.s<<" "<<dsu.l[dsu.find(idx[curr.s])]<<" "<<dsu.r[dsu.find(idx[curr.s])]<<endl;

        curr.hl=dsu.l[dsu.find(idx[curr.s])];
        curr.hr=dsu.r[dsu.find(idx[curr.s])];
    }

    dsu.init(n);
    sort(q,q+qs.size(),comp_r);
    ll r=-1;
    query prev=q[0];
    for(auto &curr:q){
        while(r<curr.r){
            r++;
            if(0<idx[r] && a[idx[r]-1]<=r) dsu.merge(idx[r],idx[r]-1);
            if(idx[r]<n-1 && a[idx[r]+1]<=r) dsu.merge(idx[r],idx[r]+1);
        }

        // cout<<curr.e<<" "<<dsu.l[dsu.find(idx[curr.e])]<<" "<<dsu.r[dsu.find(idx[curr.e])]<<endl;

        curr.wl=dsu.l[dsu.find(idx[curr.e])];
        curr.wr=dsu.r[dsu.find(idx[curr.e])];
        // cout<<curr.e<<" "<<curr.wl<<" "<<curr.wr<<endl;
        // cout<<curr.e<<" "<<prev.wl<<" "<<curr.wr<<endl;
        prev=curr;
    }

    sort(q,q+qs.size(),comp_i);
    vector<int> ans;
    for(auto curr:q){
        // cout<<curr.s<<" "<<curr.e<<" "<<curr.l<<" "<<curr.r<<": H:"<<curr.hl<<"-"<<curr.hr<<", W:"<<curr.wl<<"-"<<curr.wr<<endl;
        if(curr.s<curr.e){
            if(curr.wl<=curr.hr) ans.push_back(1);
            else ans.push_back(0);
        }
        else{
            if(curr.hl<=curr.wr) ans.push_back(1);
            else ans.push_back(0);
        }
    }
    return ans;
}

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