Submission #986482

#	Time	Username	Problem	Language	Result	Execution time	Memory
986482		yeediot	Werewolf (IOI18_werewolf)	C++17	34 / 100	304 ms	524288 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.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
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;
vector<int>adj[mxn];
int in[mxn], timer, n, ord[mxn];
vi x, y, s, e, l, r;
struct segtree{
    int seg[4*mxn], flag;
    int merge(int a,int b){
        return (flag==1?min(a,b):max(a,b));
    }
    void build(int l,int r,int id){
        if(l==r){
            seg[id]=ord[l];
            return;
        }
        int mm=l+r>>1;
        build(l,mm,id*2);
        build(mm+1,r,id*2+1);
        seg[id]=merge(seg[id*2],seg[id*2+1]);
    }
    int bs1(int l,int r,int id,int ql,int p){
        if(r<p)return n+1;
        if(flag==1){
            if(seg[id]>=ql)return n+1;
        }
        else{
            if(seg[id]<=ql)return n+1;
        }
        if(l==r)return l;
        int mm=l+r>>1;
        int x=bs1(l,mm,id*2,ql,p);
        if(x==n+1){
            return bs1(mm+1,r,id*2+1,ql,p);
        }
        else{
            return x;
        }
    }
    int bs2(int l,int r,int id,int ql,int p){
        if(l>p)return -1;
        if(flag==1){
            if(seg[id]>=ql)return -1;
        }
        else{
            if(seg[id]<=ql)return -1;
        }
        if(l==r)return l;
        int mm=l+r>>1;
        int x=bs2(mm+1,r,id*2+1,ql,p);
        if(x==-1){
            return bs2(l,mm,id*2,ql,p);
        }
        else{
            return x;
        }
    }
}mx,mn;
void dfs(int v,int pa){
    in[v]=++timer;
    ord[timer]=v;
    for(auto u:adj[v]){
        if(u!=pa)dfs(u,v);
    }
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
    n=N;
    x=X;
    y=Y;
    s=S;
    e=E;
    l=L;
    r=R;
    for(int i=0;i<n-1;i++){
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    int rt=-1;
    for(int i=0;i<n and rt==-1;i++){
        if(sz(adj[i])==1)rt=i;
    }
    dfs(rt,rt);
    mx.flag=-1;
    mn.flag=1;
    mx.build(1,n,1);
    mn.build(1,n,1);
    vector<int>ans(sz(e));
    for(int i=0;i<sz(e);i++){
        int st=s[i];
        int ed=e[i];
        int ql=l[i];
        int qr=r[i];
        pair<int,int>f={mn.bs2(1,n,1,ql,in[st]),mn.bs1(1,n,1,ql,in[st])};
        if(f.F!=in[st])f.F++;
        if(f.S!=in[st])f.S--;
        pair<int,int>s={mx.bs2(1,n,1,qr,in[ed]),mx.bs1(1,n,1,qr,in[ed])};
        if(s.F!=in[ed])s.F++;
        if(s.S!=in[ed])s.S--;
        debug(f,s);
        if(f.F>s.F)swap(f,s);
        ans[i]=f.S>=s.F;
    }
    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 'void segtree::build(int, int, int)':
werewolf.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mm=l+r>>1;
      |                ~^~
werewolf.cpp: In member function 'int segtree::bs1(int, int, int, int, int)':
werewolf.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mm=l+r>>1;
      |                ~^~
werewolf.cpp: In member function 'int segtree::bs2(int, int, int, int, int)':
werewolf.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51