Submission #92369

#	Time	Username	Problem	Language	Result	Execution time	Memory
92369		faustaadp	Pictionary (COCI18_pictionary)	C++17	140 / 140	467 ms	26704 KiB

pictionary

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,q,ta,tb,taa,tbb,p[101010],i,j,U[101010],V[101010],L[101010],R[101010],masi,jaw[101010];
vector<ll> C[101010];
void upd()
{
    ll ii;
    for(ii=1;ii<=q;ii++)
    {
        if(L[ii]<=R[ii])
        {
            C[(L[ii]+R[ii])/2].pb(ii);
            masi=1;
        }
    }
}
ll car(ll aa)
{
    if(p[aa]==aa)return aa;
    else
    {
        ll tem=car(p[aa]);
        p[aa]=tem;
        return tem;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(i=1;i<=q;i++)
    {
        cin>>U[i]>>V[i];
        L[i]=1;
        R[i]=m;
    }
    upd();
    while(masi)
    {
        masi=0;
        for(i=1;i<=n;i++)p[i]=i;
        for(i=1;i<=m;i++)
        {
            ll lom=m-i+1;
            for(j=lom;(j+lom)<=n;j+=lom)
            {
                ta=j;
                tb=j+lom;
                taa=car(ta);
                tbb=car(tb);
                if(taa!=tbb)p[taa]=tbb;
            }
            while(!C[i].empty())
            {
                ta=U[C[i].back()];
                tb=V[C[i].back()];
                taa=car(ta);
                tbb=car(tb);
                if(taa!=tbb)
                {
                    L[C[i].back()]=i+1;
                }
                else
                {
                    jaw[C[i].back()]=i;
                    R[C[i].back()]=i-1;
                }
                C[i].pop_back();
            }
        }
        upd();
    }
    for(i=1;i<=q;i++)cout<<jaw[i]<<"\n";
}

• 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