oj.uz

Submission #570423

# Submission time Handle Problem Language Result Execution time Memory
570423 2022-05-29T19:07:05 Z PedroBigMan Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 50992 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 300 ms 1052 KB Output is correct
11 Correct 221 ms 1020 KB Output is correct
12 Correct 52 ms 1108 KB Output is correct
13 Correct 330 ms 1056 KB Output is correct
14 Correct 226 ms 1028 KB Output is correct
15 Correct 271 ms 1176 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 50992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 300 ms 1052 KB Output is correct
11 Correct 221 ms 1020 KB Output is correct
12 Correct 52 ms 1108 KB Output is correct
13 Correct 330 ms 1056 KB Output is correct
14 Correct 226 ms 1028 KB Output is correct
15 Correct 271 ms 1176 KB Output is correct
16 Execution timed out 4062 ms 50992 KB Time limit exceeded
17 Halted 0 ms 0 KB -