oj.uz

Submission #1018585

# Submission time Handle Problem Language Result Execution time Memory
1018585 2024-07-10T07:13:14 Z vjudge1 Pictionary (COCI18_pictionary) C++17
140 / 140
 200 ms 22352 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10, K = 17;
vector<pair<int,int> > G[N];
int par[N][K], t[N][K], p[N], h[N];

int root(int x)
{
  if(p[x] == x) return x;
  return p[x] = root(p[x]);
}

void dfs(int v, int p = 0)
{
  h[v] = h[p] + 1;
  for(auto [u, w] : G[v])
    {
      if(u == p) continue;
      par[u][0] = v, t[u][0] = w;
      for(int i = 1; i < K; i ++)
	{
	  int inter = par[u][i - 1];
	  par[u][i] = par[inter][i - 1];
	  t[u][i] = max(t[u][i - 1], t[inter][i - 1]);
	}
      dfs(u, v);
    }
}

int query(int x, int y)
{
  int ans = 0;
  if(h[x] < h[y]) swap(x, y);

  for(int i = K - 1; i >= 0; i --)
    if(h[par[x][i]] >= h[y])
      {
	ans = max(ans, t[x][i]);
	x = par[x][i];
      }

  if(x == y) return ans;

  for(int i = K - 1; i >= 0; i --)
    if(par[x][i] != par[y][i])
      {
	ans = max(ans, max(t[x][i], t[y][i]));
	x = par[x][i];
	y = par[y][i];
      }
  ans = max(ans, max(t[x][0], t[y][0]));
  return ans;
}

int main()
{
  int n, m, q;
  cin >> n >> m >> q;

  h[0] = -1;
  iota(p, p + n + 1, 0);

  for(int i = m; i >= 1; i --)
    {
      for(int j = 2 * i; j <= n; j += i)
	{
	  if(root(j - i) == root(j)) continue;
	  G[j - i].push_back({j, m - i + 1});
	  G[j].push_back({j - i, m - i + 1});
	  p[root(j)] = root(j - i);
	}
    }

  dfs(1);

  while(q--)
    {
      int x, y;
      cin >> x >> y;
      cout << query(x, y) << '\n';
    }
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8696 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9304 KB Output is correct
2 Correct 105 ms 9296 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 9756 KB Output is correct
2 Correct 131 ms 9556 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14164 KB Output is correct
2 Correct 75 ms 14160 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14652 KB Output is correct
2 Correct 107 ms 14676 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 17488 KB Output is correct
2 Correct 83 ms 17236 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 20408 KB Output is correct
2 Correct 139 ms 20820 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 21176 KB Output is correct
2 Correct 173 ms 21868 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 22352 KB Output is correct
2 Correct 178 ms 22352 KB Output is correct