oj.uz

Submission #112763

# Submission time Handle Problem Language Result Execution time Memory
112763 2019-05-21T19:34:45 Z imaxblue Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 118780 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;
int ans[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;
  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;
  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)));
  }
  //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 {
      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, n-1){
    x = l; y = l+1;
    //cin >> x >> y;
    X.pb(x);
    Y.pb(y);
  }
  fox(l, q){
    s = 0; y = 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
*/

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19200 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 18 ms 19200 KB Output is correct
4 Correct 24 ms 19200 KB Output is correct
5 Correct 18 ms 19200 KB Output is correct
6 Correct 18 ms 19200 KB Output is correct
7 Correct 18 ms 19200 KB Output is correct
8 Correct 18 ms 19328 KB Output is correct
9 Correct 19 ms 19276 KB Output is correct
10 Correct 30 ms 20480 KB Output is correct
11 Correct 29 ms 20480 KB Output is correct
12 Correct 25 ms 20480 KB Output is correct
13 Correct 33 ms 20480 KB Output is correct
14 Correct 34 ms 20512 KB Output is correct
15 Correct 33 ms 20564 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19200 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 18 ms 19200 KB Output is correct
4 Correct 24 ms 19200 KB Output is correct
5 Correct 18 ms 19200 KB Output is correct
6 Correct 18 ms 19200 KB Output is correct
7 Correct 18 ms 19200 KB Output is correct
8 Correct 18 ms 19328 KB Output is correct
9 Correct 19 ms 19276 KB Output is correct
10 Correct 30 ms 20480 KB Output is correct
11 Correct 29 ms 20480 KB Output is correct
12 Correct 25 ms 20480 KB Output is correct
13 Correct 33 ms 20480 KB Output is correct
14 Correct 34 ms 20512 KB Output is correct
15 Correct 33 ms 20564 KB Output is correct
16 Execution timed out 4098 ms 118780 KB Time limit exceeded
17 Halted 0 ms 0 KB -