oj.uz

Submission #821723

# Submission time Handle Problem Language Result Execution time Memory
821723 2023-08-11T13:46:45 Z dungz Pictionary (COCI18_pictionary) C++17
140 / 140
 111 ms 28828 KB 
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
int par[100005],siz[100005];
vector<pair<int,int>> tree[100005];
int up[100005][25];
int h[100005];
int mx[100005][25];
int findset(int u)
{
	if(u==par[u]) return u;
	return par[u]=findset(findset(par[u]));
}
bool unite(int u,int v)
{
	u=findset(u);
	v=findset(v);
	if(u!=v)
	{
		if(siz[u]<siz[v]) swap(u,v);
		par[v]=u;
		siz[u]+=v;	
	}
	else return 0;
	return 1;
}
void dfs(int u)
{
    for(auto i:tree[u])
    {
        if(i.fi!=up[u][0])
        {
            h[i.fi]=h[u]+1;
            up[i.fi][0]=u;
            mx[i.fi][0]=i.se;
            for(int j=1;j<=20;j++)
            {
                up[i.fi][j]=up[up[i.fi][j-1]][j-1];
                mx[i.fi][j]=max(mx[i.fi][j-1],mx[up[i.fi][j-1]][j-1]);
            }
            dfs(i.fi);
        }
    }
}
int lca(int u,int v)
{
    if(h[u]!=h[v])
    {
        if(h[u]<h[v])
        {
            swap(u,v);
        }
        int k=h[u]-h[v];
        for(int i=0;(1<<i)<=k;i++)
        {
            if(k&(1<<i))
            {
                u=up[u][i];
            }
        }
    }
    if(u==v) return u;
    int k=__lg(h[u]);
    for(int i=k;i>=0;--i)
    {
        if(up[u][i]!=up[v][i])
        {
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
int cal(int u,int v)
{
    int mxx=0;
    int k=h[u]-h[v];
    for(int i=0;(1<<i)<=k;i++)
    {
        if(k&(1<<i))
        {
            mxx=max(mxx,mx[u][i]);
            u=up[u][i];
        }
    }
    return mxx;
}
int main(){
	
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		siz[i]=1;
		par[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int real=m-i+1;
		for(int j=real*2;j<=n;j+=real)
		{
			if(unite(j,j-real))
			{
				tree[j].push_back({j-real,i});
				tree[j-real].push_back({j,i});
			}
		}
	}
	dfs(1);
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		int ca=lca(x,y);
		cout<<max(cal(x,ca),cal(y,ca))<<endl;
	}
}
/*

*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2828 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2932 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3696 KB Output is correct
2 Correct 19 ms 3628 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4180 KB Output is correct
2 Correct 24 ms 3924 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8916 KB Output is correct
2 Correct 26 ms 8832 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11196 KB Output is correct
2 Correct 36 ms 12176 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15008 KB Output is correct
2 Correct 47 ms 15412 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 19136 KB Output is correct
2 Correct 73 ms 21012 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23284 KB Output is correct
2 Correct 91 ms 25912 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 28828 KB Output is correct
2 Correct 98 ms 28804 KB Output is correct