제출 #570423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570423		PedroBigMan	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4062 ms	50992 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 1000000000000000000LL
#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
    
    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, ll L, bool smaller) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
			if((smaller && adj[s][i]>L)||(!smaller && adj[s][i]<L)) {continue;}
            if(!visited[adj[s][i]]) {DFS(adj[s][i],L,smaller);}
        }
        return;
    }
};

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 Q = S.size();
	vector<ll> ans;
	REP(i,0,Q)
	{
		vector<bool> visited1,visited2;
		G.Reset(); G.DFS(S[i],L[i],false); visited1=G.visited;
		G.Reset(); G.DFS(E[i],R[i],true); visited2=G.visited;
		ll ok=0;
		REP(j,0,N) {if(visited1[j]&&visited2[j]) {ok=1;}}
		ans.pb(ok);
	}
	return ans;
}

컴파일 시 표준 에러 (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:56:17: warning: unused variable 'N' [-Wunused-variable]
   56 |     Graph() {ll N=0LL;}
      |                 ^

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