oj.uz

Submission #92369

# Submission time Handle Problem Language Result Execution time Memory
92369 2019-01-02T16:20:34 Z faustaadp Pictionary (COCI18_pictionary) C++17
140 / 140
 467 ms 26704 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4980 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11896 KB Output is correct
2 Correct 33 ms 10320 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15772 KB Output is correct
2 Correct 47 ms 13568 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 11764 KB Output is correct
2 Correct 83 ms 11380 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 12844 KB Output is correct
2 Correct 96 ms 10992 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 17304 KB Output is correct
2 Correct 171 ms 12376 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 14064 KB Output is correct
2 Correct 288 ms 19680 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 22768 KB Output is correct
2 Correct 350 ms 20960 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 26704 KB Output is correct
2 Correct 402 ms 23920 KB Output is correct