Submission #727161

#	Time	Username	Problem	Language	Result	Execution time	Memory
727161		fdnfksd	Pictionary (COCI18_pictionary)	C++14	140 / 140	343 ms	8288 KiB

pictionary

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,q;
struct qq
{
    ll a,b,low,high,mid;
}t[maxN];
ll lab[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
}
void solve()
{
    cin >> n >> m >> q;
    for(int i=1;i<=q;i++)
    {
        cin >> t[i].a >> t[i].b;
        t[i].low=0,t[i].high=m;
    }
    while(true)
    {
        for(int i=1;i<=n;i++) lab[i]=-1;
        vector<pli> a;
        for(int i=1;i<=q;i++)
        {
            if(t[i].low>t[i].high) continue;
            t[i].mid=t[i].low+t[i].high>>1;
            a.pb({t[i].mid,i});
        }
        if(a.size()==0) break;
        sort(a.begin(),a.end());
        ll j=1;
        for(int i=0;i<a.size();i++)
        {
            while(j<=a[i].fi)
            {
                ll x=m-j+1;
                for(int k=x;k<=n;k+=x)
                {
                    if(k+x<=n) unite(k,k+x);
                }
                j++;
            }
            ll id=a[i].se;
            if(findset(t[id].a)==findset(t[id].b)) t[id].high=t[id].mid-1;
            else t[id].low=t[id].mid+1;
        }
    }
    for(int i=1;i<=q;i++) cout << t[i].low<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

pictionary.cpp: In function 'void solve()':
pictionary.cpp:47:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             t[i].mid=t[i].low+t[i].high>>1;
      |                      ~~~~~~~~^~~~~~~~~~
pictionary.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<a.size();i++)
      |                     ~^~~~~~~~~

• 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