Submission #1024216

#TimeUsernameProblemLanguageResultExecution timeMemory
1024216ksu2009enWerewolf (IOI18_werewolf)C++17
34 / 100
1642 ms49356 KiB
#include "werewolf.h" #include <iostream> #include <vector> #include <string> #include <math.h> #include <cmath> #include <iomanip> #include <cstdio> #include <algorithm> #include <numeric> #include <map> #include <set> #include <queue> #include <stack> #include <deque> #include <bitset> #include <cstring> #include <unordered_map> using namespace std; typedef int ll; vector<ll> d[200007]; bool used1[200007], used2[200007]; ll lim = 0; void dfs1(ll v){ if(v < lim) return; used1[v] = true; for(auto i: d[v]){ if(!used1[i] && i >= lim) dfs1(i); } } void dfs2(ll v){ if(v > lim) return; used2[v] = true; for(auto i: d[v]){ if(!used2[i] && i <= lim) dfs2(i); } } vector<ll> ord; void dfs(ll v, ll par){ ord.push_back(v); for(auto i: d[v]) if(i != par) dfs(i, v); } ll a[200007]; pair<ll, ll> t[800007]; void build(ll v, ll l, ll r){ if(l == r){ t[v] = {a[l], a[l]}; return; } ll mid = (l + r) >> 1; build(2 * v, l, mid); build(2 * v + 1, mid + 1, r); t[v].first = min(t[2 * v].first, t[2 * v + 1].first); t[v].second = max(t[2 * v].second, t[2 * v + 1].second); } ll get(ll v, ll l, ll r, ll ql, ll qr, bool mn){ if(r < ql || qr < l) return (mn ? (ll)(1e9) : (ll)(-1e9)); if(ql <= l && r <= qr) return (mn ? t[v].first : t[v].second); ll mid = (l + r) >> 1; if(mn) return min(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn)); return max(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn)); } std::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) { ll q = l.size(); for(int i = 0; i < x.size(); i++){ d[x[i]].push_back(y[i]); d[y[i]].push_back(x[i]); } vector<int> ans; if(x.size() == n - 1){ for(int i = 0; i < n; i++){ if(d[i].size() == 1){ dfs(i, -1); break; } } vector<ll> pos(n + 1); for(int i = 0; i < n; i++){ a[i + 1] = ord[i] + 1; pos[a[i + 1]] = i + 1; } for(int i = 0; i < q; i++) s[i]++, e[i]++, l[i]++, r[i]++; build(1, 1, n); for(int i = 0; i < q; i++){ ll a = pos[s[i]], b = pos[e[i]]; ll p1 = 0, p2 = 0; ll l0 = 1, r0 = n; while(l0 < r0){ ll mid = (l0 + r0 + 1) >> 1; ll pos = 0; if(a < b) pos = a + mid - 1; else pos = a - mid + 1; if(get(1, 1, n, min(a, pos), max(a, pos), true) < l[i]){ r0 = mid - 1; } else l0 = mid; } if(a < b) p1 = a + l0 - 1; else p1 = a - l0 + 1; l0 = 1, r0 = n; while(l0 < r0){ ll mid = (l0 + r0 + 1) >> 1; ll pos = 0; if(a < b) pos = b - mid + 1; else pos = b + mid - 1; if(get(1, 1, n, min(b, pos), max(b, pos), false) > r[i]){ r0 = mid - 1; } else l0 = mid; } if(a < b) p2 = b - l0 + 1; else p2 = b + l0 - 1; // cout << l0 << endl; // cout << p1 << ' ' << p2 << endl; // cout << get(1, 1, n, 1, n, true) << endl; if(a < b){ if(p1 >= p2) ans.push_back(1); else ans.push_back(0); } else{ if(p1 <= p2) ans.push_back(1); else ans.push_back(0); } } return ans; } for(int i = 0; i < q; i++){ lim = l[i]; dfs1(s[i]); lim = r[i]; dfs2(e[i]); int res = 0; for(int j = 0; j < n; j++){ if(used1[j] && used2[j]){ res = 1; } used1[j] = used2[j] = 0; } ans.push_back(res); } return ans; } /* 6 6 3 0 3 3 1 3 4 1 2 2 5 1 5 4 2 1 2 4 2 2 2 5 4 3 4 */ /* 6 6 1 0 3 3 1 3 4 1 2 2 5 1 5 4 2 1 2 4 2 2 2 5 4 3 4 */ /* 4 3 1 3 0 0 1 1 2 3 2 2 2 */ /* 4 3 1 3 1 1 0 2 0 3 2 1 2 */

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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:106:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     if(x.size() == n - 1){
      |        ~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...