Submission #570423

#TimeUsernameProblemLanguageResultExecution timeMemory
570423PedroBigManWerewolf (IOI18_werewolf)C++14
15 / 100
4062 ms50992 KiB
/* 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; }

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:56:17: warning: unused variable 'N' [-Wunused-variable]
   56 |     Graph() {ll N=0LL;}
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...