oj.uz

Submission #465036

# Submission time Handle Problem Language Result Execution time Memory
465036 2021-08-14T22:55:01 Z soba Pictionary (COCI18_pictionary) C++14
140 / 140
 330 ms 10180 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n , m , q , a , b;
int parent[N] , siz[N] , vis[N] , dep[N];
int par[N] , edg[N];
vector<pair<int,int> >v[N];
int fnd( int node)
{
    if(parent[node]==0)
    {
        return node;
    }
    else return fnd(parent[node]);
}
int uni(int a , int b)
{
    a=fnd(a);
    b=fnd(b);
    if(a==b)
    {
        return 0;
    }
    if(siz[a]>siz[b])
    {
        parent[b]=a;
        siz[a]=siz[b]+siz[a];
    }
    else
    {
        parent[a]=b;
        siz[b]=siz[b]+siz[a];
    }
    return 1;
}
void dfs(int node , int p)
{
    for(auto u: v[node])
    {
        if(u.first!=p)
        {
            par[u.first]=node;
            edg[u.first]=u.second;
            dep[u.first]=dep[node]+1;
            dfs(u.first , node);
        }
    }
    return;
}
int main()
{
    cin >> n >> m >> q;
    for(int i = 1 ; i <N ; i++)
    {
        parent[i]=0;
        siz[i]=1;
    }
    for(int i = m ; i>0 ; i--)
    {
        for(int j = i+i ; j<=n ; j+=i)
        {
            if(uni(i , j))
            {
                v[i].push_back({j , m-i+1});
                v[j].push_back({i , m-i+1});
            }
        }
    }
    par[1]=0;
    dep[1]=0;
    dfs(1 , 0);
    while(q--)
    {
        cin >> a >> b ;
        int ans=0;
        while(a!=b)
        {
            if(dep[a]>=dep[b])
            {

                ans=max(ans , edg[a]);
                a=par[a];
            }
            else
            {

                ans=max(ans , edg[b]);
                b=par[b];
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3596 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 4296 KB Output is correct
2 Correct 158 ms 4272 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 4808 KB Output is correct
2 Correct 204 ms 4592 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5208 KB Output is correct
2 Correct 157 ms 5236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5724 KB Output is correct
2 Correct 131 ms 6136 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 6768 KB Output is correct
2 Correct 143 ms 6548 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 8124 KB Output is correct
2 Correct 267 ms 8232 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 8756 KB Output is correct
2 Correct 288 ms 9552 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 10068 KB Output is correct
2 Correct 325 ms 10180 KB Output is correct