oj.uz

Submission #112760

# Submission time Handle Problem Language Result Execution time Memory
112760 2019-05-21T19:28:34 Z imaxblue Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 129676 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 400

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

//dsu stuff
int r[200005], min_node[200005], root;
vector<int> com[200005], comu[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 <= 18; ++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;
  pre_lca[A] = vector<int>(n);
  drain(on);
  for(auto i:com[A]){
    comu[A].pb(i);
  }
  com[A].clear();
  for(auto i:comu[A]){
    //cout << i << ' ';
    on[i] = 1;
  }
  //cout << endl;
  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]){
    com[A].pb(i);
    r[i] = A;
  }
  if (com[A].size() > SZ){
    precomp(A);
  }
  return 1;
}
int check(int A, int B){
  int res = 0;
  A = r[A];
  if (pre_lca[A].size()) 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)));
  }
  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 {
      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){
    cin >> x >> y;
    X.pb(x);
    Y.pb(y);
  }
  fox(l, q){
    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
*/

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:167:7:
   fox(l, com[A].size()){
       ~~~~~~~~~~~~~~~~            
werewolf.cpp:167: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:197:7:
   fox(l, que.size()){
       ~~~~~~~~~~~~~               
werewolf.cpp:197: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 19 ms 19328 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 18 ms 19200 KB Output is correct
5 Correct 18 ms 19328 KB Output is correct
6 Correct 18 ms 19236 KB Output is correct
7 Correct 18 ms 19188 KB Output is correct
8 Correct 17 ms 19328 KB Output is correct
9 Correct 18 ms 19320 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19328 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 18 ms 19200 KB Output is correct
5 Correct 18 ms 19328 KB Output is correct
6 Correct 18 ms 19236 KB Output is correct
7 Correct 18 ms 19188 KB Output is correct
8 Correct 17 ms 19328 KB Output is correct
9 Correct 18 ms 19320 KB Output is correct
10 Correct 27 ms 20608 KB Output is correct
11 Correct 27 ms 20608 KB Output is correct
12 Correct 25 ms 20608 KB Output is correct
13 Correct 29 ms 20608 KB Output is correct
14 Correct 29 ms 20628 KB Output is correct
15 Correct 30 ms 20820 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4081 ms 129676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19328 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 18 ms 19200 KB Output is correct
5 Correct 18 ms 19328 KB Output is correct
6 Correct 18 ms 19236 KB Output is correct
7 Correct 18 ms 19188 KB Output is correct
8 Correct 17 ms 19328 KB Output is correct
9 Correct 18 ms 19320 KB Output is correct
10 Correct 27 ms 20608 KB Output is correct
11 Correct 27 ms 20608 KB Output is correct
12 Correct 25 ms 20608 KB Output is correct
13 Correct 29 ms 20608 KB Output is correct
14 Correct 29 ms 20628 KB Output is correct
15 Correct 30 ms 20820 KB Output is correct
16 Execution timed out 4081 ms 129676 KB Time limit exceeded
17 Halted 0 ms 0 KB -