Submission #117040

#TimeUsernameProblemLanguageResultExecution timeMemory
117040mirbek01Werewolf (IOI18_werewolf)C++11
0 / 100
1488 ms187580 KiB
# include <bits/stdc++.h> # include "werewolf.h" using namespace std; const int maxn = 4e5 + 2; int p[2][maxn], timer, tin[3][maxn], tout[3][maxn], up[3][19][maxn], pos[maxn], fen[maxn]; vector <int> g[3][maxn]; int f_s(int tp, int v){ return p[tp][v] == v?v:p[tp][v] = f_s(tp, p[tp][v]); } void dfs(int tp, int v, int pr){ tin[tp][v] = ++ timer; up[tp][0][v] = pr; for(int i = 1; i <= 18; i ++) up[tp][i][v] = up[tp][i - 1][ up[tp][i - 1][v] ]; for(int to : g[tp][v]){ if(to == pr) continue; dfs(tp, to, v); } tout[tp][v] = timer; } void upd(int pos){ for(; pos < maxn; pos |= pos + 1) fen[pos] ++; } int get(int r){ int ret = 0; for(; r > 0; r = (r & (r + 1)) - 1) ret += fen[r]; return ret; } 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 Q = S.size(), M = X.size(); vector<int> A(Q); for(int i = 0; i < M; i ++){ g[0][X[i]].push_back(Y[i]); g[0][Y[i]].push_back(X[i]); } for(int i = 0; i < N; i ++) p[0][i] = p[1][i] = i; for(int i = N - 1; i >= 0; i --){ for(int to : g[0][i]){ if(to < i || f_s(0, i) == f_s(0, to)) continue; int a = f_s(0, i), b = f_s(0, to); g[1][a].push_back(b); p[0][b] = a; } } for(int i = 0; i < N; i ++){ for(int to : g[0][i]){ if(to > i || f_s(1, i) == f_s(1, to)) continue; int a = f_s(1, i), b = f_s(1, to); g[2][a].push_back(b); p[1][b] = a; } } dfs(1, f_s(0, 0), f_s(0, 0)); timer = 0; dfs(2, f_s(1, 0), f_s(1, 0)); vector < pair <int, pair <int, int> > > qe; for(int i = 0; i < Q; i ++){ int s = S[i], e = E[i], l = L[i], r = R[i]; for(int j = 18; j >= 0; j --){ if(up[1][j][s] >= l) s = up[1][j][s]; } for(int j = 18; j >= 0; j --){ if(up[2][j][e] <= r) e = up[2][j][e]; } qe.push_back({tin[1][s] - 1, {-(i + 1), e}}); qe.push_back({tout[1][s], {i + 1, e}}); } sort(qe.begin(), qe.end()); for(int i = 0; i < N; i ++) pos[ tin[1][i] - 1 ] = tin[2][i]; int pt = 0; for(int i = 0; i < qe.size(); i ++){ int p = qe[i].first, id = qe[i].second.first, v = qe[i].second.second; while(pt < p) upd(pos[pt ++]); if(id < 0) A[abs(id) - 1] -= get(tout[2][v]) - get(tin[2][v]); else A[abs(id) - 1] += get(tout[2][v]) - get(tin[2][v]); } for(int i = 0; i < qe.size(); i ++) A[i] = (A[i] > 0); return A; }

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:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < qe.size(); i ++){
                      ~~^~~~~~~~~~~
werewolf.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < qe.size(); i ++)
                      ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...