oj.uz

Submission #443044

# Submission time Handle Problem Language Result Execution time Memory
443044 2021-07-09T14:13:08 Z peijar Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 63028 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;
const int MAXP = 18;

vector<int> adj[MAXN], adjMin[MAXN], adjMax[MAXN];
vector<int> S, E;
int tin[MAXN], tout[MAXN];
int curTime;
int parMin[MAXP][MAXN], parMax[MAXP][MAXN];
int nbSommets, nbAretes, nbRequetes;
vector<int> ans;
vector<int> queryAtNode[MAXN];
int idMin[MAXN], largestMin[MAXN], idMax[MAXN], smallestMax[MAXN];

void dfs(int u) {
  tin[u] = curTime++;
  for (int v : adjMin[u])
    dfs(v);
  tout[u] = curTime++;
}

set<int> dfs2(int u) {
  vector<set<int>> childs = {{tin[u]}};
  for (int v : adjMax[u]) {
    childs.push_back(dfs2(v));
  }
  for (int i = 1; i < (int)childs.size(); ++i)
    if (childs[i].size() > childs[0].size())
      swap(childs[i], childs[0]);
  for (int i = 1; i < (int)childs.size(); ++i)
    for (auto v : childs[i])
      childs[0].insert(v);
  set<int> ret = move(childs[0]);
  for (int iRequete : queryAtNode[u]) {
    auto it = ret.lower_bound(tin[S[iRequete]]);
    if (it != ret.end() and *it <= tout[S[iRequete]])
      ans[iRequete] = 1;
  }
  return ret;
}

// Min tree : We want the minimum vertex on a path to be the largest possible.

int findMin(int u) { return idMin[u] < 0 ? u : idMin[u] = findMin(idMin[u]); }

int findMax(int u) { return idMax[u] < 0 ? u : idMax[u] = findMax(idMax[u]); }

void mergeMin(int a, int b) {
  a = findMin(a), b = findMin(b);
  if (a == b)
    return;
  if (largestMin[a] < largestMin[b])
    swap(a, b);
  cerr << "Valid merge " << a << ' ' << b << ' ' << largestMin[a] << ' '
       << largestMin[b] << endl;
  parMin[0][largestMin[a]] = largestMin[b];
  adjMin[largestMin[b]].push_back(largestMin[a]);
  idMin[a] += idMin[b];
  idMin[b] = a;
  largestMin[a] = largestMin[b];
}

void mergeMax(int a, int b) {
  a = findMax(a), b = findMax(b);
  if (a == b)
    return;
  if (smallestMax[a] > smallestMax[b])
    swap(a, b);
  parMax[0][smallestMax[a]] = smallestMax[b];
  adjMax[smallestMax[b]].push_back(smallestMax[a]);
  idMax[a] += idMax[b];
  idMax[b] = a;
  smallestMax[a] = smallestMax[b];
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> _S,
                           vector<int> _E, vector<int> L, vector<int> R) {
  S = _S, E = _E;
  nbSommets = N;
  nbAretes = X.size();
  for (int i = 0; i < nbAretes; ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < nbSommets; ++i) {
    largestMin[i] = smallestMax[i] = i;
    idMin[i] = idMax[i] = -1;
  }
  for (int i = nbSommets - 1; i >= 0; --i)
    for (int j : adj[i])
      if (j > i) {
        cerr << "Merge min " << i << ' ' << j << endl;
        mergeMin(j, i);
      }
  for (int i = 0; i < nbSommets; ++i)
    for (int j : adj[i])
      if (j < i)
        mergeMax(j, i);
  parMax[0][nbSommets - 1] = nbSommets - 1;
  for (int i = 0; i < nbSommets; ++i)
    cerr << parMax[0][i] << ' ';
  cerr << endl;
  for (int i = 0; i < nbSommets; ++i)
    cerr << parMin[0][i] << ' ';
  cerr << endl;

  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < nbSommets; ++i) {
      parMax[p + 1][i] = parMax[p][parMax[p][i]];
      parMin[p + 1][i] = parMin[p][parMin[p][i]];
    }

  nbRequetes = S.size();
  for (int i = 0; i < nbRequetes; ++i)
    for (int p = MAXP - 1; p >= 0; --p)
      if (parMin[p][S[i]] >= L[i])
        S[i] = parMin[p][S[i]];
  ans.resize(nbRequetes);

  for (int i = 0; i < nbRequetes; ++i)
    for (int p = MAXP - 1; p >= 0; --p)
      if (parMax[p][E[i]] <= R[i])
        E[i] = parMax[p][E[i]];
  for (int i = 0; i < nbRequetes; ++i)
    queryAtNode[E[i]].push_back(i);
  dfs(0);
  dfs2(nbSommets - 1);
  return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19272 KB Output is correct
2 Correct 16 ms 19368 KB Output is correct
3 Correct 14 ms 19276 KB Output is correct
4 Correct 13 ms 19276 KB Output is correct
5 Correct 15 ms 19364 KB Output is correct
6 Correct 16 ms 19276 KB Output is correct
7 Correct 16 ms 19344 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 18 ms 19340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19272 KB Output is correct
2 Correct 16 ms 19368 KB Output is correct
3 Correct 14 ms 19276 KB Output is correct
4 Correct 13 ms 19276 KB Output is correct
5 Correct 15 ms 19364 KB Output is correct
6 Correct 16 ms 19276 KB Output is correct
7 Correct 16 ms 19344 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 18 ms 19340 KB Output is correct
10 Correct 102 ms 20856 KB Output is correct
11 Correct 101 ms 20836 KB Output is correct
12 Correct 105 ms 20676 KB Output is correct
13 Correct 106 ms 21652 KB Output is correct
14 Correct 102 ms 21780 KB Output is correct
15 Correct 150 ms 21072 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19272 KB Output is correct
2 Correct 16 ms 19368 KB Output is correct
3 Correct 14 ms 19276 KB Output is correct
4 Correct 13 ms 19276 KB Output is correct
5 Correct 15 ms 19364 KB Output is correct
6 Correct 16 ms 19276 KB Output is correct
7 Correct 16 ms 19344 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 18 ms 19340 KB Output is correct
10 Correct 102 ms 20856 KB Output is correct
11 Correct 101 ms 20836 KB Output is correct
12 Correct 105 ms 20676 KB Output is correct
13 Correct 106 ms 21652 KB Output is correct
14 Correct 102 ms 21780 KB Output is correct
15 Correct 150 ms 21072 KB Output is correct
16 Execution timed out 4043 ms 63028 KB Time limit exceeded
17 Halted 0 ms 0 KB -