Submission #404354

#TimeUsernameProblemLanguageResultExecution timeMemory
404354SeDunion늑대인간 (IOI18_werewolf)C++17
15 / 100
4070 ms190624 KiB
#include "werewolf.h" #include <bits/stdc++.h> #ifndef LOCAL #define cerr if(false)cerr #endif using namespace std; using ll = long long; const int MAXN = 1e6 + 11; int N, Q, M; int P[MAXN], sz, par[MAXN], val[MAXN], go[MAXN][2]; int getP(int a) { if (a == P[a]) return a; return P[a] = getP(P[a]); } vector<int>g[MAXN]; int L[MAXN], R[MAXN]; vector<int>G[2]; void dfs(int v, int t) { if (!go[v][0] && !go[v][1]) { L[v] = R[v] = G[t].size(); cerr << v << " " << t << " " << L[v] << " " << R[v] << endl; G[t].emplace_back(v); return; } dfs(go[v][0], t); dfs(go[v][1], t); L[v] = L[go[v][0]]; R[v] = R[go[v][1]]; cerr << v << " " << t << " " << L[v] << " " << R[v] << endl; } vector<int>tv[MAXN << 2]; void build(int l = 0, int r = N, int v = 1) { if (r - l == 1) { tv[v] = {G[0][l]}; return; } int m = (l + r) >> 1; build(l, m, v << 1), build(m, r, v<<1|1); tv[v].resize(r - l); merge(tv[v << 1].begin(), tv[v << 1].end(), tv[v<<1|1].begin(), tv[v<<1|1].end(), tv[v].begin()); } bool get(int L, int R, int x, int y, int l = 0, int r = N, int v = 1) { if (L >= r || l >= R) return 0; if (L <= l && r <= R) { if (tv[v].back() < x) return 0; return *lower_bound(tv[v].begin(), tv[v].end(), x) <= y; } int m = (l + r) >> 1; if (get(L, R, x, y, l, m, v << 1)) return 1; if (get(L, R, x, y, m, r, v<<1|1)) return 1; return 0; } vector<int> check_validity(int N_, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> Lq, vector<int> Rq) { N = N_; M = X.size(); Q = S.size(); for (int i = 0 ; i < M ; ++ i) { g[X[i]].emplace_back(Y[i]); g[Y[i]].emplace_back(X[i]); } sz = N; for (int i = 0 ; i < N ; ++ i) P[i] = i; for (int i = 0 ; i < N ; ++ i) { for (int j : g[i]) if (j < i) { int x = getP(i); int y = getP(j); if (x != y) { P[x] = P[y] = P[sz] = sz; go[sz][0] = x, go[sz][1] = y; par[x] = par[y] = sz; val[sz] = i; sz++; } } } dfs(sz-1, 0); int off = sz; for (int i = 0 ; i < N ; ++ i) P[i+off] = i+off; sz += N; for (int i = N-1 ; i >= 0 ; -- i) { for (int j : g[i]) if (j > i) { int x = getP(i+off); int y = getP(j+off); if (x != y) { P[x] = P[y] = P[sz] = sz; go[sz][0] = x, go[sz][1] = y; par[x] = par[y] = sz; val[sz] = i; sz++; } } } dfs(sz-1, 1); for (int &i : G[1]) i -= off; for (int i : G[0]) cerr << i << " "; cerr << ": G[0]\n"; for (int i : G[1]) cerr << i << " "; cerr << ": G[1]\n"; vector<int>id(N); for (int i = 0 ; i < N ; ++ i) { id[G[1][i]] = i; G[1][i] = i; } for (int i = 0 ; i < N ; ++ i) { G[0][i] = id[G[0][i]]; } for (int i : G[0]) cerr << i << " "; cerr << ": G[0]\n"; for (int i : G[1]) cerr << i << " "; cerr << ": G[1]\n"; build(); vector<int>ANS(Q); for (int q = 0 ; q < Q ; ++ q) { int Ls, Rs, Le, Re; { int v = E[q]; while (par[v] && val[par[v]] <= Rq[q]) v = par[v]; Le = L[v], Re = R[v]; } { int v = S[q] + off; while (par[v] && val[par[v]] >= Lq[q]) v = par[v]; Ls = L[v], Rs = R[v]; } cerr << Ls << " " << Rs << " " << Le << " " << Re << " LR" << endl; bool has = false; for (int i = Le ; i <= Re ; ++ i) { for (int j = Ls ; j <= Rs ; ++ j) { if (G[0][i] == G[1][j]) { has = true; } } } ANS[q] = get(Le, Re + 1, Ls, Rs); } return ANS; }

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:137:8: warning: variable 'has' set but not used [-Wunused-but-set-variable]
  137 |   bool has = false;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...