Submission #1073356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073356		Hugo1729	Pictionary (COCI18_pictionary)	C++17	140 / 140	58 ms	24660 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100001];
int depth[100001];
int p[100001][20];
int jump[100001][20];

void dfs(int v, int pV){
    for(auto [w,d] : adj[v]){
        if(w!=pV){
            depth[w]=depth[v]+1;
            p[w][0]=v;
            jump[w][0]=d;
            dfs(w,v);
        }
    }
}

struct DSU{
    int n;
    vector<int> e;

    DSU(int _n){
        n=_n;
        e.assign(n+1,-1);
    }

    int find(int v){
        return (e[v]<0?v:e[v]=find(e[v]));
    }

    bool join(int a, int b){
        a=find(a);b=find(b);
        if(a==b)return 0;
        if(e[a]>e[b])swap(a,b);
        e[a]+=e[b];
        e[b]=a;
        return 1;
    }
};

int dist(int a, int b){
    if(depth[a]<depth[b])swap(a,b);

    int ans=100001;

    for(int j=19;j>=0;j--){
        if((depth[a]-depth[b])&(1<<j)){
            ans=min(ans,jump[a][j]);
            a=p[a][j];
        }
    }

    if(a==b)return ans;

    for(int j=19;j>=0;j--){
        if(p[a][j]!=p[b][j]){
            ans=min(ans,min(jump[a][j],jump[b][j]));
            a=p[a][j];
            b=p[b][j];
        }
    }

    return min(ans,min(jump[a][0],jump[b][0]));
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

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

    DSU dsu(n);

    for(int i=m;i>=1;i--){
        for(int j=i*2;j<=n;j+=i){
            if(dsu.join(i,j)){
                adj[i].push_back({j,i});
                adj[j].push_back({i,i});
            }
        }
    }

    // for(int i=1;i<=n;i++){
    //     cout << i << ": ";
    //     for(auto [v,d] : adj[i])cout << '(' << v << ' ' << d << ')';
    //     cout << '\n';
    // }

    p[1][0]=1;
    depth[1]=1;
    jump[1][0]=100001;

    dfs(1,0);

    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            p[i][j]=p[p[i][j-1]][j-1];
            jump[i][j]=min(jump[i][j-1],jump[p[i][j-1]][j-1]);
        }
    }

    // for(int i=1;i<=n;i++){
    //     cout << '\n';
    //     for(int j=0;j<20;j++){
    //         cout << jump[i][j] << ' ';
    //     }
    // }

    while(q--){
        int a,b; cin >> a >> b;
        cout << max(1,m-dist(a,b)+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