oj.uz

답안 #570425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570425 2022-05-29T19:24:04 Z PedroBigMan 늑대인간 (IOI18_werewolf) C++14
34 / 100
 1192 ms 100484 KB 
/*
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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1099 ms 91764 KB Output is correct
2 Correct 1097 ms 92096 KB Output is correct
3 Correct 1105 ms 100248 KB Output is correct
4 Correct 1152 ms 100260 KB Output is correct
5 Correct 1120 ms 100440 KB Output is correct
6 Correct 1161 ms 100244 KB Output is correct
7 Correct 1077 ms 100312 KB Output is correct
8 Correct 992 ms 100456 KB Output is correct
9 Correct 466 ms 100228 KB Output is correct
10 Correct 525 ms 100232 KB Output is correct
11 Correct 574 ms 100312 KB Output is correct
12 Correct 593 ms 100264 KB Output is correct
13 Correct 1178 ms 100484 KB Output is correct
14 Correct 1133 ms 100364 KB Output is correct
15 Correct 1192 ms 100308 KB Output is correct
16 Correct 1109 ms 100252 KB Output is correct
17 Correct 1095 ms 100216 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -