제출 #990166

#제출 시각아이디문제언어결과실행 시간메모리
990166vqpahmad늑대인간 (IOI18_werewolf)C++14
15 / 100
174 ms120148 KiB
#include "werewolf.h" #include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9 + 7; const int MAXN = 2e5 + 15; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; struct MergeTree { int p[MAXN], s[MAXN], lebal[MAXN]; int cur_node; vector<int> adj[MAXN]; void init(int n){ cur_node = n; for (int i = 0; i < n; i++){ p[i] = i; s[i] = 1; lebal[i] = i; } } int find(int u){ if (p[u] == u) return u; return p[u] = find(p[u]); } void merge(int u, int v){ u = find(u); v = find(v); if (u == v) return; adj[cur_node].pb(lebal[u]); adj[cur_node].pb(lebal[v]); adj[lebal[u]].pb(cur_node); adj[lebal[v]].pb(cur_node); if (s[u] < s[v]) swap(u, v); s[u] += s[v]; p[v] = u; lebal[u] = cur_node++; } int st[MAXN], ft[MAXN], timer = 1; int mn[MAXN], mx[MAXN]; // for humans I need min, for werewolf max int fa[MAXN][20]; void dfs(int node, int par){ st[node] = timer++; fa[node][0] = par; for (int b = 1; b < 20; b++){ fa[node][b] = fa[fa[node][b - 1]][b - 1]; } if (sz(adj[node]) == 1 && adj[node][0] == par){ mx[node] = node; mn[node] = node; } for (auto to : adj[node]){ if (to != par){ dfs(to, node); ckmax(mx[node], mx[to]); ckmin(mn[node], mn[to]); } } ft[node] = timer++; } void get_dfs_order(){ cur_node--; for (int i = 0; i <= cur_node; i++){ mn[i] = inf; mx[i] = -inf; } dfs(cur_node, cur_node); } pii find_range(int u, int time, bool human){ for (int b = 19; b >= 0; b--){ if (human && mn[fa[u][b]] >= time){ u = fa[u][b]; } if (!human && mx[fa[u][b]] <= time){ u = fa[u][b]; } } return {st[u], ft[u]}; } void dbg(){ cout << "HERE\n"; for (int i = 0; i <= cur_node; i++){ cout << i << ' ' << st[i] << ' ' << ft[i] << ' ' << mn[i] << ' ' << mx[i] << endl; } } } human, werewolf; const int off = (1<<18); struct sgt { #define ls (idx<<1) #define rs (idx<<1|1) int t[off<<1]; void update(int idx, int u){ t[idx+=off] += u; while (idx/=2) t[idx] = t[ls] + t[rs]; } int get(int l, int r, int idx=1, int lo=0, int hi=off){ if (r <= lo || hi <= l) return 0; if (l <= lo && hi <= r) return t[idx]; int mi = (lo+hi)>>1; return get(l, r, ls, lo, mi)+get(l, r, rs, mi, hi); } } seg; vector<int> adj[MAXN]; 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 = sz(X); int Q = S.size(); for (int i = 0; i < m; i++){ adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]); } werewolf.init(n); for (int i = 0; i < n; i++){ // I want to caclute component for werewolf for L <= i for (auto u : adj[i]){ if (u <= i){ werewolf.merge(i, u); } } } human.init(n); for (int i = n - 1; i >= 0; i--){ // I want to caclute component for werewolf for L <= i for (auto u : adj[i]){ if (u >= i){ human.merge(i, u); } } } werewolf.get_dfs_order(); human.get_dfs_order(); //werewolf.dbg(); //human.dbg(); vector<int> add[MAXN]; for (int i = 0; i < n; i++){ add[human.st[i]].pb(werewolf.st[i]); } vector<array<int, 4>> Queries[MAXN]; // type, bot, top, idx for (int i = 0; i < Q; i++){ pii hr = human.find_range(S[i], L[i], 1); pii wr = werewolf.find_range(E[i], R[i], 0); Queries[hr.F - 1].pb({-1, wr.F, wr.S, i}); Queries[hr.S].pb({1, wr.F, wr.S, i}); } vector<int> ans(Q); for (int i = 0; i < MAXN; i++){ for (auto pos : add[i]){ seg.update(pos, 1); } for (auto [type, bot, top, idx] : Queries[i]){ ans[idx] += type * seg.get(bot, top); } } for (int i = 0; i < Q; ++i) { ans[i] = !!ans[i]; } return ans; }

컴파일 시 표준 에러 (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:170:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  170 |   for (auto [type, bot, top, idx] : Queries[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...