Submission #1213448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213448		Zbyszek99	Werewolf (IOI18_werewolf)	C++20	100 / 100	714 ms	152676 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct dsu
{
    int P[400'001];
    int cost[400'001];
    vi sons[400'001];
    int jump[400'001][19];
    int cur_v = 200'001;
    
    int pre[400'001];
    int max_pre[400'001];
    int cur_pre = 0;
    dsu()
    {
        rep(i,400'001) 
        {
            P[i] = i;
            jump[i][0] = i;
        }
    }
    int fint(int v)
    {
        if(P[v] == v) return v;
        P[v] =  fint(P[v]);
        return P[v];
    }
    void onion(int a, int b, int c)
    {
        a = fint(a);
        b = fint(b);
        if(a == b) return;
        P[a] = cur_v;
        P[b] = cur_v;
        cost[a] = c;
        cost[b] = c;
        cost[cur_v] = c;
        jump[a][0] = cur_v;
        jump[b][0] = cur_v;
        sons[cur_v].pb(a);
        sons[cur_v].pb(b);
        cur_v++;
    }
    void dfs(int v)
    {
        pre[v] = cur_pre++;
        max_pre[v] = pre[v];
        forall(it,sons[v])
        {
            dfs(it);
            max_pre[v] = max_pre[it];
        }
    }
    void calc_tree()
    {
        rep2(bit,1,18)
        {
            rep(i,400'001)
            {
                jump[i][bit] = jump[jump[i][bit-1]][bit-1];
            }
        }
        rep(i,400'001)
        {
            if(P[i] == i)
            {
                dfs(i);
            }
        }
    }
};

struct event
{
    int type, x, y1,y2,ind;
    bool operator<(const event& other)
    {
        if(x != other.x) return x < other.x;
        return type < other.type;
    }
};

const int tree_siz = 1024*1024-1;
int drzewo[tree_siz+1];

int get_sum(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return 0;
    if(p1 >= s1 && p2 <= s2) return drzewo[akt];
    return get_sum(akt*2,p1,(p1+p2)/2,s1,s2) + get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}

void upd(int v)
{
    drzewo[v] = drzewo[v*2] + drzewo[v*2+1];
    if(v != 1) upd(v/2);
}

void change(int ind)
{
    drzewo[tree_siz/2+1+ind]++;
    upd((tree_siz/2+1+ind)/2);
}

dsu dsu_human;
dsu dsu_wolf;

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) 
{  
    vector<pair<int,pii>> edges_H;
    vector<pair<int,pii>> edges_W;
    rep(i,siz(X))
    {
        edges_H.pb({min(X[i],Y[i]),{X[i],Y[i]}});
        edges_W.pb({max(X[i],Y[i]),{X[i],Y[i]}});
    }
    sort(all(edges_H));
    sort(all(edges_W));
    reverse(all(edges_H));
    forall(it,edges_W)
    {
        //cout << it.ss.ff << " " << it.ss.ss << " W\n";
        dsu_wolf.onion(it.ss.ff,it.ss.ss,it.ff);
    } 
    forall(it,edges_H)
    {
      //  cout << it.ss.ff << " " << it.ss.ss << " H\n";
        dsu_human.onion(it.ss.ff,it.ss.ss,it.ff);
    } 
    dsu_human.calc_tree();
    dsu_wolf.calc_tree();
    vector<event> events;
    rep(i,siz(S))
    {
        int beg = S[i];
        for(int bit = 18; bit >= 0; bit--)
        {
            if(dsu_human.cost[dsu_human.jump[beg][bit]] >= L[i])
            {
                beg = dsu_human.jump[beg][bit];
            }
        }
        if(dsu_human.cost[beg] >= L[i]) beg = dsu_human.jump[beg][0];
        int en = E[i];
        for(int bit = 18; bit >= 0; bit--)
        {
            if(dsu_wolf.cost[dsu_wolf.jump[en][bit]] <= R[i])
            {
             //   cout << dsu_wolf.cost[dsu_wolf.jump[en][bit]] << " " << dsu_wolf.jump[en][bit] << " " << en << " en_jump\n"; 
                en = dsu_wolf.jump[en][bit];
            }
        }
      //  cout << dsu_wolf.cost[en] << " last_jump\n";
        if(dsu_wolf.cost[en] <= R[i]) en = dsu_wolf.jump[en][0];
      //  cout << beg << " " << dsu_human.pre[beg] - 200'000 << " " << dsu_human.max_pre[beg] - 200'000 << " beg\n";
      //  cout << en << " " << dsu_wolf.pre[en] - 200'000 << " " << dsu_wolf.max_pre[en] - 200'000 << " end\n";
        events.pb({1,dsu_human.pre[beg]-1,dsu_wolf.pre[en],dsu_wolf.max_pre[en],i});
        events.pb({2,dsu_human.max_pre[beg],dsu_wolf.pre[en],dsu_wolf.max_pre[en],i});
    }
    rep(i,n)
    {
      //  cout << dsu_human.pre[i] - 200'000 << " " << dsu_wolf.pre[i] - 200'000 << " pre\n";
        events.pb({0,dsu_human.pre[i],dsu_wolf.pre[i],dsu_wolf.pre[i],-1});
    }
    sort(all(events));
    vi ans(siz(S));
    forall(it,events)
    {
     //   cout << it.type << " " << it.x << " " << it.y1 << " " << it.y2 << " " << it.ind << " " << get_sum(1,0,tree_siz/2,it.y1,it.y2) << " events\n";
        if(it.type == 0) change(it.y1);
        else
        {
            if(it.type == 1)
            {
                ans[it.ind] = get_sum(1,0,tree_siz/2,it.y1,it.y2);
            }
            else
            {
                if(ans[it.ind] == get_sum(1,0,tree_siz/2,it.y1,it.y2))
                {
                    ans[it.ind] = 0;
                }
                else
                {
                    ans[it.ind] = 1;
                }
            }
        }
    }
    return ans;
}

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