제출 #1275353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275353		aats411	Pictionary (COCI18_pictionary)	C++20	140 / 140	88 ms	33352 KiB

pictionary

#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

// template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #define int long long

// #pragma once
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

typedef long long ll;
#define ld long double
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const int N = 200005, M = 317;
// const int inf = 1e18 + 7;
const ld pi = acos(-1);
// const ll inf = 1e9 + 5;

int n, ara[N];
vector<int> parent(N);
vector<int> adj[N];
vector<int> tin(N), tout(N);
int timer = 0;
vector<vector<int>> up(N, vector<int> (21));


void make_set(int v)
{
    parent[v] = v;
}

int find_set(int v){
    if(parent[v]==v) return v;
    return parent[v] = find_set(parent[v]);
}

void union_set(int u, int v, int val)
{
    int up = find_set(u);
    int vp = find_set(v); 
    if(up == vp){
        ++n;
        adj[n].push_back(up);
        make_set(n);
        parent[up] = n;
        ara[n] = val;
    } 
    else{
        ++n;
        adj[n].push_back(up);
        adj[n].push_back(vp);
        make_set(n);
        parent[up] = parent[vp] = n;
        ara[n] = val;
    }  

}

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= 20; ++i)
        if(up[v][i-1] != 0) up[v][i] = up[up[v][i-1]][i-1];
        else up[v][i] = 0;

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 20; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}


int32_t main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int tt = 1;
    // cin >> tt;
    for(int tc=1; tc<=tt; tc++){
        
        // cout << "Case " << tc << ": ";

        int m, q;
        cin >> n >> m >> q;
        int fn = n;

        for(int i=1; i<=n; i++) make_set(i);

        for(int i=m; i>=1; i--){
            for(int j=2*i; j<=fn; j+=i){
                if(find_set(i) != find_set(j)) union_set(i, j, i);
            }
        }

        dfs(n, n);

        while(q--){
            int a, b;
            cin >> a >> b;
            int lc = lca(a, b);
            cout << m - ara[lc] + 1 << "\n";
        }

    }


    return 0;
        
}

• 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