Submission #570425

#	Time	Username	Problem	Language	Result	Execution time	Memory
570425		PedroBigMan	Werewolf (IOI18_werewolf)	C++14	34 / 100	1192 ms	100484 KiB

werewolf

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "werewolf.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 10000000
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<bool> visited; //for DFS/BFS
	vector<ll> current;
    
    Graph() {ll N=0LL;}
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
		current.pb(s);
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
        }
        return;
    }
};

template<class T=ll>
class SparseTable_min //Range Minimum Queries
{
    public:
    ll N; 
    vector<T> a;
    vector<vector<T> > v;
    
    SparseTable_min() {N=0LL;}
    SparseTable_min(vector<T> b)
    {
        a=b; N=a.size();
        ll lo=(ll) floor((ld) log2(N)) +1LL;
        vector<T> xx; 
        REP(i,0,lo) {xx.pb(INF);} REP(i,0,N) {v.pb(xx);}
        REP(step,0LL,lo)
        {
            REP(i,0,N-(1LL<<step)+1LL)
            {
                if(step==0) {v[i][0]=a[i];}
                else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
            }
        }
    }
    
    T query(ll l, ll r)
    {
        ll step=(ll) floor((ld) log2(r-l+1LL));
        return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
    }
};

template<class T=ll>
class SparseTable_max //Range Minimum Queries
{
    public:
    ll N; 
    vector<T> a;
    vector<vector<T> > v;
    
    SparseTable_max() {N=0LL;}
    SparseTable_max(vector<T> b)
    {
        a=b; N=a.size();
        ll lo=(ll) floor((ld) log2(N)) +1LL;
        vector<T> xx; 
        REP(i,0,lo) {xx.pb(0);} REP(i,0,N) {v.pb(xx);}
        REP(step,0LL,lo)
        {
            REP(i,0,N-(1LL<<step)+1LL)
            {
                if(step==0) {v[i][0]=a[i];}
                else {v[i][step]=max(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
            }
        }
    }
    
    T query(ll l, ll r)
    {
        ll step=(ll) floor((ld) log2(r-l+1LL));
        return max(v[l][step],v[r-(1LL<<step)+1LL][step]);
    }
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) 
{
	ll M = X.size();
	vector<vector<ll> > adj; VV(adj,N,{}); 
	REP(i,0,M) {adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);}
	Graph G(adj); ll s; REP(i,0,N) {if(adj[i].size()==1) {s=i; break;}}
	G.DFS(s);
	vector<ll> p = G.current;
	unordered_map<ll,ll> m; REP(i,0,N) {m[p[i]]=i;}
	ll Q = S.size();
	vector<ll> ans;
	SparseTable_max<ll> S_max(p); SparseTable_min<ll> S_min(p);
	REP(i,0,Q)
	{
		ll A = m[S[i]]; ll B = m[E[i]];
		ll C,D; ll lo,hi,mid;
		if(A<=B)
		{
			//C is last after A prefix >= L[i]
			//D is first before B suffix <= R[i]
			lo=A,hi=B; 
			while(lo<hi)
			{
				mid=(lo+hi+1)/2;
				if(S_min.query(A,mid)>=L[i]) {lo=mid;} 
				else {hi=mid-1;}
			}
			C=lo;
			lo=A,hi=B; 
			while(lo<hi)
			{
				mid=(lo+hi)/2;
				if(S_max.query(mid,B)<=R[i]) {hi=mid;} 
				else {lo=mid+1;}
			}
			D=lo;
			if(C>=D) {ans.pb(1);} else {ans.pb(0);}
		}
		else
		{
			//C is first before A suffix >= L[i]
			//D is last after B prefix <= R[i]
			lo=B,hi=A; 
			while(lo<hi)
			{
				mid=(lo+hi+1)/2;
				if(S_max.query(B,mid)<=R[i]) {lo=mid;} 
				else {hi=mid-1;}
			}
			D=lo;
			lo=B,hi=A; 
			while(lo<hi)
			{
				mid=(lo+hi)/2;
				if(S_min.query(mid,A)>=L[i]) {hi=mid;} 
				else {lo=mid+1;}
			}
			C=lo;
			if(C<=D) {ans.pb(1);} else {ans.pb(0);}
		}
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
werewolf.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
werewolf.cpp: In constructor 'Graph::Graph()':
werewolf.cpp:57:17: warning: unused variable 'N' [-Wunused-variable]
   57 |     Graph() {ll N=0LL;}
      |                 ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:71:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |         if(visited[s]) {return;}
      |                     ^
werewolf.cpp:151:19: note: 's' was declared here
  151 |  Graph G(adj); ll s; REP(i,0,N) {if(adj[i].size()==1) {s=i; break;}}
      |                   ^

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