oj.uz

Submission #727161

# Submission time Handle Problem Language Result Execution time Memory
727161 2023-04-20T06:15:17 Z fdnfksd Pictionary (COCI18_pictionary) C++14
140 / 140
 343 ms 8288 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 624 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1632 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5124 KB Output is correct
2 Correct 62 ms 5324 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6940 KB Output is correct
2 Correct 97 ms 6368 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3644 KB Output is correct
2 Correct 98 ms 3620 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 3908 KB Output is correct
2 Correct 92 ms 4116 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 5756 KB Output is correct
2 Correct 133 ms 3928 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 6924 KB Output is correct
2 Correct 220 ms 6756 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 7280 KB Output is correct
2 Correct 247 ms 7388 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 8288 KB Output is correct
2 Correct 277 ms 8100 KB Output is correct