oj.uz

Submission #586804

# Submission time Handle Problem Language Result Execution time Memory
586804 2022-06-30T17:16:35 Z perchuts Pictionary (COCI18_pictionary) C++17
140 / 140
 134 ms 32324 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int par[maxn], lvl[maxn], cnv[5*maxn];


vector<ii>pl[maxn];
vector<int>comp[maxn];

int findp(int x){return par[x] = (par[x]==x?x:findp(par[x]));}

void merge(int x,int y,int t){
    x = findp(x), y = findp(y);
    if(x==y)return;
    if(lvl[x]<lvl[y])swap(x,y);
    par[y] = x;
    if(lvl[x]==lvl[y])lvl[x]++;
    for(auto z:comp[y]){
        comp[x].pb(z);
        pl[z].pb({t,x});
    }
}

int main(){_
    int n,m,q;cin>>n>>m>>q;
    int cur = 1;
    for(int i=1;i<=n;++i)par[i] = i, comp[i].pb(i), pl[i].pb({0,i});
    for(int i=m;i>=1;--i){
        for(int j=2*i;j<=n;j+=i){
            merge(j,j-i,cur);
            cnv[cur++] = m-i+1;
        }
    }    
    for(int i=1;i<=n;++i)reverse(all(pl[i]));
    while(q--){
        int u,v;cin>>u>>v;
        assert(findp(u)==findp(v));
        bool ok = 0;
        for(int i=0;i<min(sz(pl[u]),sz(pl[v]));++i){
            if(pl[u][i]!=pl[v][i]){
                cout<<cnv[max(pl[u][i].first,pl[v][i].first)]<<endl;
                ok = 1;
                break;
            }
        }
        if(!ok)cout<<0<<endl;
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14696 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15316 KB Output is correct
2 Correct 23 ms 15272 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15700 KB Output is correct
2 Correct 27 ms 15556 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 18528 KB Output is correct
2 Correct 36 ms 18464 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 20060 KB Output is correct
2 Correct 44 ms 19688 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22676 KB Output is correct
2 Correct 51 ms 22744 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21524 KB Output is correct
2 Correct 77 ms 26820 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 28440 KB Output is correct
2 Correct 113 ms 30016 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 32324 KB Output is correct
2 Correct 125 ms 32012 KB Output is correct