Submission #243389

#TimeUsernameProblemLanguageResultExecution timeMemory
243389ant101Werewolf (IOI18_werewolf)C++14
0 / 100
225 ms28152 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <fstream> #include <cmath> #include <vector> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <stack> #include <queue> #include <assert.h> #include <limits> #include <cstdio> #include <complex> #include "werewolf.h" using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef string str; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; #define mp make_pair #define f first #define s second typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; typedef vector<str> vs; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<pd> vpd; #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define rsz resize #define ins insert #define ft front() #define bk back() #define pf push_front #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) const int MOD = 1e9+7; // 998244353; // = (119<<23)+1 const int MX = 6e3+5; const ll INF = 1e18; const ld PI = 4*atan((ld)1); const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; ll vis[MX]; ll vis2[MX]; ll cl, cr; vector<ll> adj[MX]; void dfs1(ll u) { trav(v, adj[u]) { if (!vis[v] && v>=cl) { vis[v] = true; dfs1(v); } } } void dfs2(ll u) { trav(v, adj[u]) { if (!vis2[v] && v<=cr) { vis2[v] = true; dfs2(v); } } } std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { int Q = S.size(); F0R (i, sz(X)) { adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]); } std::vector<int> A(Q); for (int i = 0; i < Q; ++i) { memset(vis, 0, sizeof(vis)); memset(vis2, 0, sizeof(vis2)); cl = L[i]; cr = R[i]; if (S[i]>=L[i]) { dfs1(S[i]); } if (E[i]<=R[i]) { dfs2(E[i]); } bool cango = false; F0R (j, N) { if (vis[j] && vis2[j] && j >= cl && j <= cr) { cango = true; break; } } A[i] = cango; } return A; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...