Submission #1018585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018585		vjudge1	Pictionary (COCI18_pictionary)	C++17	140 / 140	200 ms	22352 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14