Submission #432861

#	Time	Username	Problem	Language	Result	Execution time	Memory
432861		Bench0310	Werewolf (IOI18_werewolf)	C++17	100 / 100	1441 ms	119000 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
typedef long long ll;

const int N=200005;

struct DSU
{
    int n;
    int root;
    vector<int> p;
    vector<int> sz;
    vector<vector<int>> g;
    vector<int> tin;
    vector<int> tout;
    int tcnt;
    vector<array<int,18>> up;
    int edges;
    DSU(int nn,int r)
    {
        n=nn;
        root=r;
        edges=n-1;
        tcnt=0;
        p.assign(n,0);
        for(int i=0;i<n;i++) p[i]=i;
        sz.assign(n,1);
        g.resize(n);
        tin.assign(n,-1);
        tout.assign(n,-1);
        up.resize(n);
        for(int i=0;i<n;i++) up[i].fill(-1);
    }
    int find_set(int a)
    {
        if(a==p[a]) return a;
        else return (p[a]=find_set(p[a]));
    }
    void merge_sets(int a,int b) //a should be parent if mergeable
    {
        a=find_set(a);
        b=find_set(b);
        if(a==b) return;
        g[a].push_back(b);
        p[b]=a;
        sz[a]+=sz[b];
        if((--edges)==0) dfs(root);
    }
    void dfs(int a)
    {
        tin[a]=tcnt++;
        for(int i=1;i<18;i++)
        {
            if(up[a][i-1]==-1) break;
            up[a][i]=up[up[a][i-1]][i-1];
        }
        for(int to:g[a])
        {
            up[to][0]=a;
            dfs(to);
        }
        tout[a]=tcnt-1;
    }
    int find_up(int a,auto f)
    {
        for(int i=17;i>=0;i--) if(up[a][i]!=-1&&f(up[a][i])==1) a=up[a][i];
        return a;
    }
};

vector<int> tree(4*N,0);

void update(int idx,int l,int r,int pos,int x)
{
    if(l==r) tree[idx]+=x;
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx]=tree[2*idx]+tree[2*idx+1];
    }
}

int query(int idx,int l,int r,int ql,int qr)
{
    if(ql>qr) return 0;
    if(l==ql&&r==qr) return tree[idx];
    int m=(l+r)/2;
    return query(2*idx,l,m,ql,min(qr,m))+query(2*idx+1,m+1,r,max(ql,m+1),qr);
}

vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r)
{
    int m=x.size();
    int q=s.size();
    vector<int> v[n];
    for(int i=0;i<m;i++)
    {
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    DSU one(n,0);
    for(int i=n-1;i>=0;i--)
    {
        for(int to:v[i]) if(to>i) one.merge_sets(i,to);
    }
    DSU two(n,n-1);
    for(int i=0;i<n;i++)
    {
        for(int to:v[i]) if(to<i) two.merge_sets(i,to);
    }
    vector<array<int,2>> points(n);
    for(int i=0;i<n;i++) points[i]={one.tin[i],two.tin[i]};
    vector<int> add[n];
    for(int i=0;i<n;i++) add[points[i][0]].push_back(points[i][1]);
    vector<int> res(q,0);
    vector<array<int,4>> queries[n]; //l,r,id,d
    for(int i=0;i<q;i++)
    {
        int u=one.find_up(s[i],[&](int a)->bool{return (a>=l[i]);});
        int lone=one.tin[u];
        int rone=one.tout[u];
        u=two.find_up(e[i],[&](int a)->bool{return (a<=r[i]);});
        int ltwo=two.tin[u];
        int rtwo=two.tout[u];
        if(lone>0) queries[lone-1].push_back({ltwo,rtwo,i,-1});
        queries[rone].push_back({ltwo,rtwo,i,1});
    }
    for(int i=0;i<n;i++)
    {
        for(int a:add[i]) update(1,0,n-1,a,1);
        for(auto [a,b,id,d]:queries[i]) res[id]+=(d*query(1,0,n-1,a,b));
    }
    for(int i=0;i<q;i++) res[i]=(res[i]>0);
    return res;
}

//int main()
//{
//    
//    return 0;
//}

Compilation message (stderr)

werewolf.cpp:66:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   66 |     int find_up(int a,auto f)
      |                       ^~~~

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