Submission #987072

#	Time	Username	Problem	Language	Result	Execution time	Memory
987072		yeediot	Werewolf (IOI18_werewolf)	C++17	100 / 100	1749 ms	144860 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include "werewolf.h"
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn=2e5+5;
const int inf=1e9;
int n, root[mxn];
struct tree{
    vector<int>adj[mxn];
    vector<tuple<int,int,int>>edges;
    int flg, cnt, jump[20][mxn], timer, in[mxn], out[mxn], ord[mxn];
    struct DSU{
        int to[mxn],num[mxn];
        void init(){
            for(int i=0;i<mxn;i++){
                to[i]=i;
                num[i]=1;
            }
        }
        int find(int x){
            return (x==to[x]?x:to[x]=find(to[x]));
        }
    }d;
    void dfs(int v,int pa){
        in[v]=++timer;
        ord[timer]=v;
        jump[0][v]=pa;
        for(auto u:adj[v]){
            if(u!=pa)dfs(u,v);
        }
        out[v]=timer;
    }
    void build_tree(int f){
        flg=f;
        d.init();
        cnt=n;
        if(flg)sort(all(edges));
        else sort(all(edges),greater<tuple<int,int,int>>());
        for(auto [c,x,y]:edges){
            int fx=d.find(x),fy=d.find(y);
            if(fx==fy)continue;
            if((flg and x>y) or (!flg and x<y)){
                swap(x,y);
                swap(fx,fy);
            }
            adj[fy].pb(fx);
            d.to[fx]=fy;
        }
        if(flg){
            dfs(n,n);
        }
        else{
            dfs(1,1);
        }
        for(int i=1;i<20;i++){
            for(int j=1;j<=n;j++){
                jump[i][j]=jump[i-1][jump[i-1][j]];
            }
        }
    }
    int find(int st,int x){
        if(flg){
            for(int i=19;i>=0;i--){
                if(jump[i][st]<=x){
                    st=jump[i][st];
                }
            }
        }
        else{
            for(int i=19;i>=0;i--){
                if(jump[i][st]>=x){
                    st=jump[i][st];
                }
            }
        }
        return st;
    }
}mn, mx;
struct segtree{
    struct node{
        int l,r,c;
    }seg[mxn<<5];
    int cnt=0;
    int build(int l,int r){
        int node=++cnt;
        seg[node].c=0;
        if(l==r){
            return node;
        }
        int mm=l+r>>1;
        seg[node].l=build(l,mm);
        seg[node].r=build(mm+1,r);
        return node;
    }
    int modify(int from,int l,int r,int p){
        int node=++cnt;
        seg[node]=seg[from];
        if(l==r){
            seg[node].c++;
            return node;
        }
        int mm=l+r>>1;
        if(p<=mm){
            seg[node].l=modify(seg[node].l,l,mm,p);
        }
        else{
            seg[node].r=modify(seg[node].r,mm+1,r,p);
        }
        seg[node].c=seg[seg[node].l].c+seg[seg[node].r].c;
        return node;
    }
    int query(int v,int u,int l,int r,int ql,int qr){
        if(qr<l or r<ql){
            return 0;
        }
        if(ql<=l and r<=qr){
            return seg[u].c-seg[v].c;
        }
        int mm=l+r>>1;
        return query(seg[v].l,seg[u].l,l,mm,ql,qr)+query(seg[v].r,seg[u].r,mm+1,r,ql,qr);
    }
}tr;
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
    n=N;
    vector<int>ans(sz(E));
    for(int i=0;i<sz(X);i++){
        int a=X[i],b=Y[i];
        a++;
        b++;
        mn.edges.pb({max(a,b),a,b});
        mx.edges.pb({min(a,b),a,b});
    }
    mn.build_tree(1);
    mx.build_tree(0);
    root[0]=tr.build(1,n);
    for(int i=1;i<=n;i++){
        root[i]=tr.modify(root[i-1],1,n,mn.in[mx.ord[i]]);
    }
    for(int i=0;i<sz(S);i++){
        int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
        int fs=mx.find(s,l),se=mn.find(e,r);
        ans[i]=(tr.query(root[mx.in[fs]-1],root[mx.out[fs]],1,n,mn.in[se],mn.out[se])>0);
    }
    return ans;
}
#ifdef local
int main(){
    why_TOI_is_so_de;
    int n, m, q;
    cin>>n>>m>>q;
    vi x(m),y(m),s(q),e(q),l(q),r(q);
    for(int i=0;i<m;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<q;i++){
        cin>>s[i]>>e[i]>>l[i]>>r[i];
    }
    vi temp=check_validity(n,x,y,s,e,l,r);
    for(auto i:temp){
        cout<<i<<'\n';
    }
}
#endif
/*
input:
 
*/















 

Compilation message (stderr)

werewolf.cpp: In member function 'int segtree::build(int, int)':
werewolf.cpp:132:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mm=l+r>>1;
      |                ~^~
werewolf.cpp: In member function 'int segtree::modify(int, int, int, int)':
werewolf.cpp:144:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |         int mm=l+r>>1;
      |                ~^~
werewolf.cpp: In member function 'int segtree::query(int, int, int, int, int, int)':
werewolf.cpp:161:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |         int mm=l+r>>1;
      |                ~^~
werewolf.cpp: In function 'void setIO(std::string)':
werewolf.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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