oj.uz

Submission #112768

# Submission time Handle Problem Language Result Execution time Memory
112768 2019-05-21T20:08:22 Z imaxblue Werewolf (IOI18_werewolf) C++17
100 / 100
 2996 ms 210864 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
#define SZ 800

int n, m, c=0, q, p[200005];
int ans[200005];

//dsu stuff
int r[200005], min_node[200005], root;
vector<int> com[200005], comu[200005], com3[200005];

//tree stuff
int d[200005], lo[400005], hi[400005], node[400005];
int anc[20][400005];
int lg[400005];
vector<int> tree[200005];
vector<pii> edge;
vector<pair<pii, p3i> > que;
vector<int> pre_lca[200005];


bool mrg(int A, int B){
  //cout << "*" << A << ' ' <<B << ' ';
  A = r[A]; B = r[B];
  //cout << A << ' '  << B << endl;
  if (A == B) return 0;
  if (com[A].size() < com[B].size()) return mrg(B, A);
  for(auto i:com[B]){
    com[A].pb(i);
    r[i] = A;
  }
  //cout << A << ' ' << B << ' ' << min_node[A] << ' ' << min_node[B] << endl;
  tree[min_node[A]].pb(min_node[B]);
  tree[min_node[B]].pb(min_node[A]);
  min_node[A] = min(min_node[A], min_node[B]);
  return 1;
}

void dfs(int N, int P){
  if (P != -1) d[N] = d[P]+1;
  p[N]=P;
  node[lo[N] = hi[N] = c++] = N;
  for(auto nxt:tree[N]){
    if (nxt == P) continue;
    dfs(nxt, N);
    node[hi[N] = c++] = N;
  }
  //cout << N << ' ' << P << ' ' << lo[N] << ' ' << hi[N] << endl;
}
void build(){
  fox(l, n){
    r[l] = l;
    min_node[l] = l;
    com[l] = vector<int>({l});
  }
  sort(edge.rbegin(), edge.rend());
  fox(l, m){
    mrg(edge[l].x, edge[l].y);
  }
  dfs(0, -1);
  fox(l, 2*n){
    //cout << node[l] << ' ';
    anc[0][l] = node[l];
    for (int l2 = 1; l2 <= 19; ++l2){
      if ((l + 1 - (1<<l2) < 0)) break;
      anc[l2][l] = min(anc[l2-1][l], anc[l2-1][l - (1<<(l2-1))]);
    }
  }
  //cout << endl;
}
int get_anc(int A, int B){
  if (lo[A] > lo[B]) return get_anc(B, A);
  if (hi[A] > hi[B]) return A;
  int lft = hi[A], rit = lo[B];
  int len = lg[rit - lft + 1];
  //cout << "*" << lft <<' ' << rit << ' ' << len << endl;
  return min(anc[len][rit], anc[len][lft + (1<<len) - 1]);
}
bool on[200005];
void dfs2(int N, int P){
  for (auto i:tree[N]){
    if (i == P) continue;
    dfs2(i, N);
    on[N]|=on[i];
  }
}
void dfs3(int N, int P, int B){
  if (on[N]) B = N;
  for (auto i:tree[N]){
    if (i == P) continue;
    dfs3(i, N, B);
  }
  pre_lca[root][N] = B;
}
void precomp(int A){
  root = A;
  if (pre_lca[A].empty())pre_lca[A] = vector<int>(n);
  drain(on);
  com3[A].clear();
  com3[A].pb(A);
  for(auto i:com[A]){
    comu[A].pb(i);
  }
  com[A].clear();
  //return;
  for(auto i:comu[A]){
    //cout << i << ' ';
    on[i] = 1;
  }
  fox1r(l, n-1){
    on[p[l]]|=on[l];
  }
  pre_lca[A][0]=0;
  fox1(l, n-1){
    pre_lca[A][l]=(on[l]?l:pre_lca[A][p[l]]);
  }
  //dfs2(0, -1);
  //dfs3(0, -1, 0);
  //fox(l, n)  cout << on[l] << ' '; cout << endl;
  //fox(l, n)  cout << pre_lca[A][l] << ' '; cout << endl;
}
bool mrg2(int A, int B){
  A = r[A]; B = r[B];
  if (A == B) return 0;
  if (com[A].size() + comu[A].size() < com[B].size() + comu[B].size()) return mrg2(B, A);

  //cout << A << ' ' << B << endl;
  for(auto i:com[B]){
    com[A].pb(i);
    r[i] = A;
  }
  for(auto i:comu[B]){
    comu[A].pb(i);
    r[i] = A;
  }
  for (auto i:com3[B]){
    com3[A].pb(i);
  }
  if (com[A].size() > SZ){
    precomp(A);
  }
  return 1;
}
int check(int A, int B){
  int res = 0;
  A = r[A];
  for(auto i:com3[A]){
    //cout << pre_lca[i][B] << endl;
    res = max(res, pre_lca[i][B]);
  }
  //res = pre_lca[A][B];
  fox(l, com[A].size()){
    //cout << com[A][l] << ' ' << B << ' ' << get_anc(com[A][l], B) << endl;
    res = max(res, get_anc(com[A][l], B));
  }
  //cout << "%" << res << endl;
  return res;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  m = X.size();
  n = N;
  lg[0] = -1;
  fox1(l, 2*N){
    lg[l] = lg[l/2]+1;
  }
  fox(l, m){
    if (X[l] > Y[l]) swap(X[l], Y[l]);
    edge.pb(mp(X[l], Y[l]));
    que.pb(mp(mp(Y[l], -X[l]), mp(mp(-1, -1), -1)));
  }
  build();
  q = S.size();
  fox(l, q){
    que.pb(mp(mp(R[l], L[l]), mp(mp(S[l], E[l]), l)));
    //cout << L[l] << ' ' << R[l] << ' ' << S[l] << ' ' << E[l] << endl;
  }
  //return vector<int>();
  fox(l, n){
    r[l] = l;
    com[l] = vector<int>({l});
    comu[l] = vector<int>();
  }
  sort(que.begin(), que.end());
  fox(l, que.size()){
    int y = que[l].x.x, x = que[l].x.y, s = que[l].y.x.x, e = que[l].y.x.y, i = que[l].y.y;
    if (s == -1){
      x*=-1;
      mrg2(x, y);
    } else {
      //cout << "*" << x << ' ' << y << ' ' << s << ' ' << e << endl;
      if (e > y || s < x){
        ans[i] = 0;
        continue;
      }
      ans[i] = (check(e, s) >= x);
      //cout << "^" << i << ' ' << x << endl;
    }
  }
  vector<int> ans2 = vector<int>();
  fox(l, q ) ans2.pb(ans[l]);
  return ans2;
}
/*
int32_t main(){
  int n, m, q, s, e, x, y;
  vector<int> X, Y, S, E, L, R;
  cin >> n >> m >> q;
  fox(l, m){
    x = l; y = l+1;
    cin >> x >> y;
    X.pb(x);
    Y.pb(y);
  }
  fox(l, q){
    s = 0; e = n-1; x = 0; y = n-1;
    cin >> s >> e >> x >> y;
    S.pb(s);
    E.pb(e);
    L.pb(x);
    R.pb(y);
  }
  vector<int> v = check_validity(n, X, Y, S, E, L, R);
  cout << v.size() << endl;
  fox(l, v.size()) cout << v[l] << ' '; cout << endl;
  return 0;
}*/
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
200000 199999 200000
*/

Compilation message

werewolf.cpp: In function 'int check(int, int)':
werewolf.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
werewolf.cpp:183:7:
   fox(l, com[A].size()){
       ~~~~~~~~~~~~~~~~            
werewolf.cpp:183:3: note: in expansion of macro 'fox'
   fox(l, com[A].size()){
   ^~~
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:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
werewolf.cpp:215:7:
   fox(l, que.size()){
       ~~~~~~~~~~~~~               
werewolf.cpp:215:3: note: in expansion of macro 'fox'
   fox(l, que.size()){
   ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23936 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 79 ms 23932 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 21 ms 23936 KB Output is correct
7 Correct 21 ms 24004 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 21 ms 23936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23936 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 79 ms 23932 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 21 ms 23936 KB Output is correct
7 Correct 21 ms 24004 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 21 ms 23936 KB Output is correct
10 Correct 33 ms 25208 KB Output is correct
11 Correct 31 ms 25208 KB Output is correct
12 Correct 28 ms 25216 KB Output is correct
13 Correct 37 ms 25208 KB Output is correct
14 Correct 38 ms 25208 KB Output is correct
15 Correct 34 ms 25308 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 201792 KB Output is correct
2 Correct 1149 ms 105640 KB Output is correct
3 Correct 1187 ms 106164 KB Output is correct
4 Correct 1443 ms 109036 KB Output is correct
5 Correct 1308 ms 109940 KB Output is correct
6 Correct 1376 ms 124200 KB Output is correct
7 Correct 1333 ms 210864 KB Output is correct
8 Correct 1105 ms 105676 KB Output is correct
9 Correct 958 ms 105932 KB Output is correct
10 Correct 1053 ms 108040 KB Output is correct
11 Correct 858 ms 108312 KB Output is correct
12 Correct 1226 ms 122740 KB Output is correct
13 Correct 1038 ms 109864 KB Output is correct
14 Correct 1038 ms 110256 KB Output is correct
15 Correct 1070 ms 110328 KB Output is correct
16 Correct 1044 ms 109948 KB Output is correct
17 Correct 1357 ms 204448 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23936 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 79 ms 23932 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 21 ms 23936 KB Output is correct
7 Correct 21 ms 24004 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 21 ms 23936 KB Output is correct
10 Correct 33 ms 25208 KB Output is correct
11 Correct 31 ms 25208 KB Output is correct
12 Correct 28 ms 25216 KB Output is correct
13 Correct 37 ms 25208 KB Output is correct
14 Correct 38 ms 25208 KB Output is correct
15 Correct 34 ms 25308 KB Output is correct
16 Correct 1258 ms 201792 KB Output is correct
17 Correct 1149 ms 105640 KB Output is correct
18 Correct 1187 ms 106164 KB Output is correct
19 Correct 1443 ms 109036 KB Output is correct
20 Correct 1308 ms 109940 KB Output is correct
21 Correct 1376 ms 124200 KB Output is correct
22 Correct 1333 ms 210864 KB Output is correct
23 Correct 1105 ms 105676 KB Output is correct
24 Correct 958 ms 105932 KB Output is correct
25 Correct 1053 ms 108040 KB Output is correct
26 Correct 858 ms 108312 KB Output is correct
27 Correct 1226 ms 122740 KB Output is correct
28 Correct 1038 ms 109864 KB Output is correct
29 Correct 1038 ms 110256 KB Output is correct
30 Correct 1070 ms 110328 KB Output is correct
31 Correct 1044 ms 109948 KB Output is correct
32 Correct 1357 ms 204448 KB Output is correct
33 Correct 1766 ms 131856 KB Output is correct
34 Correct 756 ms 72228 KB Output is correct
35 Correct 1916 ms 111416 KB Output is correct
36 Correct 1485 ms 124556 KB Output is correct
37 Correct 1982 ms 109372 KB Output is correct
38 Correct 1663 ms 119384 KB Output is correct
39 Correct 2622 ms 106612 KB Output is correct
40 Correct 2118 ms 123820 KB Output is correct
41 Correct 1438 ms 113504 KB Output is correct
42 Correct 1104 ms 117548 KB Output is correct
43 Correct 1754 ms 115648 KB Output is correct
44 Correct 1843 ms 113292 KB Output is correct
45 Correct 1517 ms 106448 KB Output is correct
46 Correct 1479 ms 106560 KB Output is correct
47 Correct 1075 ms 110156 KB Output is correct
48 Correct 1121 ms 110096 KB Output is correct
49 Correct 1058 ms 110144 KB Output is correct
50 Correct 1036 ms 109864 KB Output is correct
51 Correct 2067 ms 123916 KB Output is correct
52 Correct 2996 ms 123948 KB Output is correct