제출 #1219241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219241		jahongir	Pictionary (COCI18_pictionary)	C++20	140 / 140	78 ms	26184 KiB

pictionary

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
                    tree_order_statistics_node_update>;

#define ll long long
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define all(a) a.begin(),a.end()

// #define int ll

const int mxn = 2e5+10, lg2 = 18;
vector<int> g[mxn];
int suc[mxn][lg2], val[mxn];
int tin[mxn], tout[mxn], tim;

struct DSU{
    vector<int> par; int cur;

    void init(int n){
        par = vector<int>(2*n+10,-1);
        cur = n;
    }

    int get(int u){
        if(par[u]<0) return u;
        return par[u] = get(par[u]);
    }

    bool merge(int u, int v, int i){
        u = get(u), v = get(v);
        if(u==v) return false;
        val[++cur] = i;
        par[cur] = par[u] + par[v];
        par[u] = par[v] = cur;
        g[cur].pb(u); g[cur].pb(v);
        return true;
    }
};

void dfs(int u){
    tin[u] = tim++;
    for(int i = 1; i < lg2; i++)
        suc[u][i] = suc[suc[u][i-1]][i-1];

    for(auto v : g[u]){
        suc[v][0] = u;
        dfs(v);
    }
    tout[u] = tim;
}

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

int getlca(int u, int v){
    if(isanc(u,v)) return u;
    if(isanc(v,u)) return v;

    for(int i = lg2-1; i >= 0; i--)
        if(!isanc(suc[u][i],v))
            u = suc[u][i];

    return suc[u][0];
}

void solve(){
    int n,m,q; cin >> n >> m >> q;

    DSU dsu; dsu.init(n);

    for(int i = m; i; i--){
        for(int j = 2*i; j <= n; j+=i)
            dsu.merge(i,j,m-i+1);
    }

    suc[dsu.cur][0] = dsu.cur;
    dfs(dsu.cur);


    while(q--){
        int u,v; cin >> u >> v;
        cout << val[getlca(u,v)] << '\n';
    }
}


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while(t--) solve();
}

• 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