Submission #1038811

#TimeUsernameProblemLanguageResultExecution timeMemory
1038811Mr_HusanboyWerewolf (IOI18_werewolf)C++17
15 / 100
4061 ms22400 KiB
#include "werewolf.h" #include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(a) (a).begin(), (a).end() #define ll long long template<typename T> int len(T &a){return a.size();} mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); struct DSU{ vector<int> par, sz; int n; DSU (int _n){ n = _n; par.resize(n); iota(all(par), 0); sz.assign(n, 1); } DSU (){} int get(int a){ return (par[a] == a ? a : par[a] = get(par[a])); } void init(int _n){ n = _n; par.resize(n); iota(all(par), 0); sz.assign(n, 1); } void unite(int a, int b){ a = get(a); b = get(b); if(a == b) return; if(sz[a] < sz[b]) swap(a,b); sz[a] += sz[b]; par[b] = a; } void link(int a, int b){ a = get(a); b = get(b); if(a == b) return; sz[b] += sz[a]; par[a] = b; } }; int n, m, q; vector<vector<int>> g; 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) { n = N; q = len(s); m = len(x); vector<int> res(q); for(int i = 0; i < m; i ++) if(x[i] > y[i]) swap(x[i], y[i]); for(int i = 0; i < q; i ++){ DSU hum(n), wolf(n); for(int j = 0; j < m; j ++){ if(x[j] >= l[i]){ hum.unite(y[j], x[j]); // cout << x[j] << ' ' << y[j]; } if(y[j] <= r[i]){ wolf.unite(x[j], y[j]); } } //cout << endl; bool ok = 0; for(int j = l[i]; j <= r[i]; j ++){ if(hum.get(j) != hum.get(s[i])) continue; if(wolf.get(j) != wolf.get(e[i])) continue; ok = 1; break; } res[i] = ok; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...