Submission #294644

#	Time	Username	Problem	Language	Result	Execution time	Memory
294644		Autoratch	Werewolf (IOI18_werewolf)	C++14	34 / 100	3399 ms	66936 KiB

werewolf

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

const int N = 1 << 18;

int n,m,q,st,en;
vector<int> adj[N];
int idx[N],wha[N];

struct node
{
    int mn,mx;
    friend node operator+(const node &a,const node &b)
    {
        node ret;
        ret.mx = max(a.mx,b.mx);
        ret.mn = min(a.mn,b.mn);
        return ret;
    }
}tree[N << 1];

void dfs(int u,int p,int k)
{
    idx[u] = k,wha[k] = u;
    for(int v : adj[u]) if(v!=p) dfs(v,u,k+1);
}

void build(int l,int r,int idx)
{
    if(l==r) return void(tree[idx] = {wha[l],wha[l]});
    int m = (l+r)/2;
    build(l,m,idx*2),build(m+1,r,idx*2+1);
    tree[idx] = tree[idx*2]+tree[idx*2+1];
}

node read(int l,int r,int idx,int x,int y)
{
    if(x>r or y<l) return {INT_MAX,INT_MIN};
    if(x<=l and y>=r) return tree[idx];
    int m = (l+r)/2;
    return read(l,m,idx*2,x,y)+read(m+1,r,idx*2+1,x,y);
}

int ltorx(int l,int r,int mn,int mx)
{
    int lx = l;
    while(l<r)
    {
        int m = (l+r+1)/2;
        if(read(0,n-1,1,lx,m).mn>=mn) l = m;
        else r = m-1;
    }
    return l;
}

int ltorn(int l,int r,int mn,int mx)
{
    int lx = l;
    while(l<r)
    {
        int m = (l+r+1)/2;
        if(read(0,n-1,1,lx,m).mx<=mx) l = m;
        else r = m-1;
    }
    return l;
}

int rtolx(int l,int r,int mn,int mx)
{
    int rx = r;
    while(l<r)
    {
        int m = (l+r)/2;
        if(read(0,n-1,1,m,rx).mn>=mn) r = m;
        else l = m+1;
    }
    return l;
}

int rtoln(int l,int r,int mn,int mx)
{
    int rx = r;
    while(l<r)
    {
        int m = (l+r)/2;
        if(read(0,n-1,1,m,rx).mx<=mx) r = m;
        else l = m+1;
    }
    return l;
}

vector<int> check_validity(int _n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r)
{
    n = _n,m = x.size(),q = s.size();
    for(int i = 0;i < m;i++)
    {
        int a = x[i],b = y[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 0;i < n;i++) if(adj[i].size()==1) st = i;
    dfs(st,st,0);
    build(0,n-1,1);
    vector<int> ans;
    for(int i = 0;i < q;i++)
    {
        int fl,fr;
        if(idx[s[i]]<idx[e[i]]) fl = ltorx(idx[s[i]],idx[e[i]],l[i],n-1),fr = rtoln(idx[s[i]],idx[e[i]],0,r[i]);
        else fl = ltorn(idx[e[i]],idx[s[i]],0,r[i]),fr = rtolx(idx[e[i]],idx[s[i]],l[i],n-1);
        ans.push_back(fl>=fr);
    }
    return ans;
}

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