Submission #991592

#TimeUsernameProblemLanguageResultExecution timeMemory
991592LalicWerewolf (IOI18_werewolf)C++17
15 / 100
422 ms21076 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define mp make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 3005; int pai[2][MAXN], peso[2][MAXN]; int find(int tipo, int x){ return (pai[tipo][x]==x ? x : pai[tipo][x]=find(tipo, pai[tipo][x])); } void join(int tipo, int a, int b){ a=find(tipo, a); b=find(tipo, b); if(a==b) return; if(peso[tipo][a]>peso[tipo][b]) swap(a, b); pai[tipo][a]=b; peso[tipo][b]=max(peso[tipo][b], peso[tipo][a]+1); } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int m=(int)X.size(), q=(int)L.size(); vector<int> ans(q); for(int i=0;i<q;i++){ for(int j=0;j<N;j++){ pai[0][j]=pai[1][j]=j; peso[0][j]=peso[1][j]=0; } for(int j=0;j<m;j++){ if(max(X[j], Y[j])<=R[i]) join(1, X[j], Y[j]); if(min(X[j], Y[j])>=L[i]) join(0, X[j], Y[j]); } ans[i]=0; for(int j=0;j<N;j++){ if(find(0, S[i])==find(0, j) && find(1, E[i])==find(1, j)){ ans[i]=1; break; } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...