제출 #1246146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246146		Dedibeat	Pictionary (COCI18_pictionary)	C++20	140 / 140	123 ms	3220 KiB

pictionary

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}

int32_t main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> sz(n + 1, 1), t(n + 1), par(n + 1);
    int timer = 0;
    auto get = [&](int v)
    {
        while(v != par[v])
            v = par[v];
        return v;
    };

    for(int i = 0; i <= n; i++)
        par[i] = i;
    auto link = [&](int u, int v)
    {
        //cout << "link " << u << " " << v << endl;
        u = get(u); v = get(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        t[v] = timer;
    };

    while(m > 0)
    {
        timer++;
        for(int i = m; i + m <= n; i += m)
            link(i, i + m);
        m--;
    }

    function<int(int, int)> answer = [&](int u, int v)
    {
        if(u == v) return 0LL;
        if(sz[u] >= sz[v]) 
            return max(t[v], answer(u, par[v]));
        else 
            return max(t[u], answer(par[u], v));
    };

    while(q--)
    {
        int u, v;
        cin >> u >> v;
        cout << answer(u, v) << "\n";
    }


}

• 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