Submission #635665

#	Time	Username	Problem	Language	Result	Execution time	Memory
635665		Khoa	Pictionary (COCI18_pictionary)	C++14	140 / 140	44 ms	3308 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

void print() {cerr << '\n';} template <typename T, typename... Args>
void print(const T &a, const Args &...args) { cerr << a << ' ', print(args...); }
const int N = 2e5 + 5;
 
int n, m, q, par[N], w[N], sz[N];
 
int anc(int u)
{
    return u == par[u] ? u : anc(par[u]);
}
 
void join(int u, int v, int weight)
{
    u = anc(u), v = anc(v);
    if (u == v) return;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
    w[u] = weight;
}
 
int Getmax(int u, int v)
{
    int ans = 0;
    while (u != v)
    {
        if (w[u] > w[v]) swap(u, v);
        ans = w[u];
        u = par[u];
    }
    return ans;
}
 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    
    for(int i = 1; i <= n; i++) sz[i] = 1, par[i] = i, w[i] = 1e9;
    for(int i = m; i >= 1; i--)
    {
        for(int j = i; j <= n; j += i)
            join(i, j, m - i + 1);
    }
    
    while(q--)
    {
        int u, v;
        cin >> u >> v;
        cout << Getmax(u, v) << '\n';
    }
    return 0;
}
/*
nhận xét tất cả các đỉnh có gcd bằng M nối với nhau đồng nghĩa với việc tất cả các đỉnh chia hết cho M đểu thuộc 
cùng một thành phần liên thông
*/

• 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