제출 #76410

#제출 시각아이디문제언어결과실행 시간메모리
76410born2rule늑대인간 (IOI18_werewolf)C++14
15 / 100
1054 ms20908 KiB
#include <bits/stdc++.h> #include "werewolf.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define db long double #define ii pair<int,int> #define vi vector<int> #define fi first #define se second #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define pb push_back #define mp make_pair #define FN(i, n) for (int i = 0; i < (int)(n); ++i) #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i) #define rep(i,a,b) for(int i=a;i<b;i++) #define repv(i,a,b) for(int i=b-1;i>=a;i--) #define SET(A, val) memset(A, val, sizeof(A)) typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ; // order_of_key (val): returns the no. of values less than val // find_by_order (k): returns the kth largest element.(0-based) #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif const int N=200005; vi v[N]; bool vis[N]; void dfs(int u,int l,int r,vi &tmp,int type=0) { if(type==0 && u<l) return; if(type==1 && u>r) return; vis[u]=true; tmp.pb(u); for(int v1:v[u]) { if(vis[v1]) continue; dfs(v1,l,r,tmp,type); } } vi subtask12(int n,vi S,vi E,vi L,vi R) { int q=sz(S); vi ans(q,0); rep(i,0,q) { int x=S[i],y=E[i],l=L[i],r=R[i]; if(x<l || y>r) continue; vi tmp1,tmp2; rep(j,0,n) vis[j]=false; dfs(x,l,r,tmp1); rep(j,0,n) vis[j]=false; dfs(y,l,r,tmp2,1); sort(all(tmp1)); sort(all(tmp2)); bool ok=false; for(int x:tmp1) { int ind=lower_bound(all(tmp2),x)-tmp2.begin(); if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true; } if(ok) ans[i]=1; } return ans; } vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R) { int q=sz(S); rep(i,0,sz(X)) { v[X[i]].pb(Y[i]); v[Y[i]].pb(X[i]); } if(n<=3000 && q<=3000) return subtask12(n,S,E,L,R); return S; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...