Submission #1270211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270211		sasde	Werewolf (IOI18_werewolf)	C++20	0 / 100	355 ms	77804 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time   cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e6+5,lg=30,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,1,-1};
vector<int>ver[N],g[N];
int tin[N],tout[N],timer,tmp[N];
ii P[N];
iv val[N];
int r[N],n;
vector<int>req[N];
struct BIT
{
  int n,z=0;
  vector<int>bit,s;
  BIT(){};
  BIT(int _n):n(_n),bit(n+5,0),s(n+5,0),z(0){};
  void check(int &idx){
    if(s[idx]!=z){
      bit[idx]=0;
      s[idx]=z;
    }
  }
  void update(int idx,int val){
    while(idx<=n){
      check(idx);
      bit[idx]+=val;
      idx+=idx&-idx;
    }
  }
  int get(int idx){
    int res=0;
    while(idx>0){
      check(idx);
      res+=bit[idx];
      idx-=idx&-idx;
    }
    return res;
  }
  void updaterange(int u,int v,int val){
    update(u,val);
    update(v+1,-val);
  }
  int getrange(int u,int v){
    if(v<u)return 0;
    return get(v)-get(u-1);
  }
};
int acs(int u){
    return r[u]==u?u:r[u]=acs(r[u]);
}
void join(int u,int v){
    u=acs(u);
    v=acs(v);
    if(u==v)return;
    ++n;
    r[u]=r[v]=r[n]=n;
    g[n].emb(u);
    g[n].emb(v);
}
void dfs(int u){
    tin[u]=++timer;
    // cout <<u<<" ";
    for(auto v:g[u]){
        dfs(v);
    }
    tout[u]=timer;
}
void process(int &node,vector<int> &S, vector<int> &E, vector<int>&L, vector<int> &R){
    memset(r,-1,sizeof r);
    for(int i=1;i<=node;++i)r[i]=i;
    int query=sz(S);
    for(int i=0;i<query;++i){
        req[L[i]].emb(i);
    }
    n=node;
    for(int i=node;i>=1;--i){
        for(auto x:ver[i]){
            if(x>i)join(i,x);
        }
        for(auto x:req[i]){
            tmp[x]=acs(S[x]);
        }
    }
    dfs(n);
    for(int i=1;i<=node;++i)P[i].fi=tin[i];
    for(int i=0;i<query;++i){
        // cout <<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';

        val[i].fi={tin[tmp[i]],tout[tmp[i]]};
    }

}  
void process1(int &node,vector<int> &S, vector<int> &E, vector<int>&L, vector<int> &R){
    memset(r,-1,sizeof r);
    for(int i=1;i<=node;++i)r[i]=i;
    int query=sz(S);
    for(int i=1;i<=n;++i){
        req[i].clear();
        g[i].clear();
    }
    for(int i=0;i<query;++i){
        req[R[i]].emb(i);
    }
    n=node;
    for(int i=1;i<=node;++i){
        for(auto x:ver[i]){
            if(x<i)join(i,x);
        }
        for(auto x:req[i]){
            tmp[x]=acs(E[x]);
        }
    }
    timer=0;
    dfs(n);
    // cout<<n<<'\n';
    for(int i=1;i<=node;++i)P[i].se=tin[i];
    for(int i=0;i<query;++i){
        // cout <<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';

        // cout <<tmp[i]<<" "<<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';
        val[i].se={tin[tmp[i]],tout[tmp[i]]};
    }
    for(int i=1;i<=node;++i){
        req[i].clear();
        g[i].clear();
    }
}  
struct pt{
    int d,c,i,t;
};
vector<pt>h[N];
bool M2;
vector<int> check_validity(int node, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>L, vector<int> R){
    for(int i=0;i<sz(X);++i){
        ++X[i];
        ++Y[i];
        ver[X[i]].emb(Y[i]);
        ver[Y[i]].emb(X[i]);
    }
    for(int i=0;i<sz(S);++i){
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
        // cout <<S[i]<<" "<<E[i]<<" "<<L[i]<<" "<<R[i]<<'\n';
    }
    process(node,S,E,L,R);
    process1(node,S,E,L,R);
    int query=sz(S);
    vector<int>ans(query);
    for(int i=0;i<query;++i){
        auto[x,y]=val[i];
        h[x.fi-1].pb({x.se-1,y.se,i,-1});
        h[y.fi].pb({x.se-1,y.se,i,1});
        // cout <<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<'\n';
    }
    BIT bit(n);
    sort(P+1,P+1+node);
    for(int i=1;i<=node;++i){
        bit.update(P[i].se,1);
        for(auto x:h[P[i].fi]){
            ans[x.i]+=x.t*bit.getrange(x.d,x.c);
        }
    }
    for(auto &x:ans)x=(x>0);
    return ans;

}
// main()
// {
//   srand(time(0));
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     #define task "aws"
//     if(fopen(task".inp","r")){
//       freopen(task".inp","r",stdin);
//       freopen(task".out","w",stdout);
//     }
//     int node,edge,query;
//     cin >> node >> edge >> query;
//     vector<int>x,y,s,e,l,r;
//     for(int i=1;i<=edge;++i){
//         int u,v;
//         cin >> u >> v;
//         x.emb(u);
//         y.emb(v);
//         // cout <<u<<" "<<v<<'\n';
//     }
//     for(int i=1;i<=query;++i){
//         int st,ed,li,ri;
//         cin >> st >> ed >> li >>ri;
//         s.emb(st);
//         e.emb(ed);
//         l.emb(li);
//         r.emb(ri);
//     }
//     vector<int>ans=check_validity(node,x,y,s,e,l,r);
//     for(auto x:ans)cout << x<<'\n';
// look_memory;
// look_time;
// }

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