Submission #1047180

#TimeUsernameProblemLanguageResultExecution timeMemory
1047180Alihan_8Werewolf (IOI18_werewolf)C++17
15 / 100
4054 ms63488 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(), x.end() #define ln '\n' struct Dsu{ vector <int> fa, _in, _out, euler; vector <vector<int>> adj; bool isMax; Dsu(int n, bool isMax) : isMax(isMax) { fa.resize(n); iota(all(fa), 0); adj.resize(n); _in.resize(n); _out.resize(n); } int get(int u){ return u ^ fa[u] ? fa[u] = get(fa[u]) : u; } bool f(int u, int v){ return isMax ? u > v : u < v; } bool merge(int u, int v){ u = get(u), v = get(v); if ( u == v ) return false; if ( !f(u, v) ) swap(u, v); fa[v] = u; adj[u].pb(v); return true; } void RunDfs(){ int ct = -1; auto dfs = [&](auto dfs, int u) -> void{ _in[u] = ++ct; euler.pb(u); for ( auto &v: adj[u] ){ //~ cout << u << " " << v << ln; dfs(dfs, v); } _out[u] = ct; }; int root = get(0); dfs(dfs, root); } }; 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 n = N, m = X.size(), q = S.size(); // Subtask #3 vector <vector<int>> adj(n); for ( int i = 0; i < m; i++ ){ adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]); } Dsu ds(n, 0), de(n, 1); vector <int> ps(q), pe(q); { // for S[i] vector <vector<int>> qu(n); for ( int i = 0; i < q; i++ ){ qu[L[i]].pb(i); } for ( int u = n - 1; u >= 0; u-- ){ for ( auto &v: adj[u] ){ if ( v > u ){ ds.merge(u, v); } } for ( auto &j: qu[u] ){ ps[j] = ds.get(S[j]); } } } { // for E[i] vector <vector<int>> qu(n); for ( int i = 0; i < q; i++ ){ qu[R[i]].pb(i); } for ( int u = 0; u < n; u++ ){ for ( auto &v: adj[u] ){ if ( v < u ){ de.merge(u, v); } } for ( auto &j: qu[u] ){ pe[j] = de.get(E[j]); } } } ds.RunDfs(); de.RunDfs(); vector <int> ans(q); for ( int i = 0; i < q; i++ ){ for ( int j = ds._in[ps[i]]; j <= ds._out[ps[i]]; j++ ){ // subtree of pe[i] for ( int k = de._in[pe[i]]; k <= de._out[pe[i]]; k++ ){ // subtree of pe[i] if ( ds.euler[j] == de.euler[k] ){ ans[i] = 1; } } } } 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...