제출 #1311141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311141		ja_tausf	Pictionary (COCI18_pictionary)	C++20	140 / 140	127 ms	29440 KiB

pictionary

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vll vector<ll>
#define vpl vector<pair<long long, long long>>
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lmax LONG_LONG_MAX
#define lmin LONG_LONG_MIN
#define mxn 200007
#define endl <<'\n'
// #pragma GCC target("sse4")
// #pragma GCC target ("sse4.2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("03")
// #pragma GCC optimize("unroll loops")

ll t, n, m, k, w;
string s, s1;
const int mod = 1e9 + 7;

vector<vll> reTree;
vector <int> ans;
struct RT
{
    int n; // size of the reTree, (V + E)
    vector <int> par;
    RT (int n) : n(n)
    {
        par = ans = vector <int>(n + 1);
        reTree = vector <vll>(n + 1);
        iota(par.begin(), par.end(), 0);
    }
    inline int find(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = find(par[x]);
    }
    void build()
    { //{w, u, v} 1 based
        // sort(e.begin(), e.end());
        int id = n / 2;
        for (int i = m; i >= 1; i--)
        {
            for (ll z = i; z <= n / 2; z += i)
            {
                int u = i, v = z;
                u = find(u), v = find(v);
                if (u == v)
                {
                    continue;
                }
                par[u] = par[v] = ++id;
                ans[id] = m - i + 1;
                w = id;
                reTree[id].push_back(u);
                reTree[id].push_back(v);
            }
        }
    }
};

const int LG = 20, N = 2e5 + 7;
int par[N][21], dep[N], sz[N];

void dfs (int u, int p = 0)
{
    par[u][0] = p;
    dep[u] = 1 + dep[p];
    sz[u] = 1;
    for (int i = 1; i <= LG; i++)
    {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for (auto &&v : reTree[u])
    {
        if (v == p)
        {
            continue;
        }
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int lca (int u, int v)
{
    if (dep[u] < dep[v])
    {
        swap(u, v);
    }
    for (int k = LG - 1; k >= 0; k--)
    {
        if (dep[par[u][k]] >= dep[v])
        {
            u = par[u][k];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int k = LG - 1; k >= 0; k--)
    {
        if (par[u][k] != par[v][k])
        {
            u = par[u][k];
            v = par[v][k];
        }
    }
    return par[u][0];
}


signed main()
{
    _fastio;
    ll tc = 0;
    // cin >> t;
    // while (t--)
    // { 
        cin >> n >> m >> k;
        RT rt(2 * n);
        rt.build();
        dfs(w);
        while (k--)
        {
            ll u, v;
            cin >> u >> v;
            ll lc = lca(u, v);
            cout << ans[lc] << '\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