oj.uz

Submission #635665

# Submission time Handle Problem Language Result Execution time Memory
635665 2022-08-26T15:47:57 Z Khoa Pictionary (COCI18_pictionary) C++14
140 / 140
 44 ms 3308 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1108 KB Output is correct
2 Correct 15 ms 1104 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1480 KB Output is correct
2 Correct 20 ms 1356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1280 KB Output is correct
2 Correct 15 ms 1236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1500 KB Output is correct
2 Correct 19 ms 1536 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2052 KB Output is correct
2 Correct 26 ms 1652 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2380 KB Output is correct
2 Correct 32 ms 2508 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2756 KB Output is correct
2 Correct 36 ms 2860 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3292 KB Output is correct
2 Correct 44 ms 3308 KB Output is correct