Submission #821723

#	Time	Username	Problem	Language	Result	Execution time	Memory
821723		dungz	Pictionary (COCI18_pictionary)	C++17	140 / 140	111 ms	28828 KiB

pictionary

#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 / 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