oj.uz

Submission #1073356

# Submission time Handle Problem Language Result Execution time Memory
1073356 2024-08-24T13:09:21 Z Hugo1729 Pictionary (COCI18_pictionary) C++17
140 / 140
 58 ms 24660 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7256 KB Output is correct
2 Correct 16 ms 7260 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7516 KB Output is correct
2 Correct 23 ms 7384 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12268 KB Output is correct
2 Correct 19 ms 12124 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14760 KB Output is correct
2 Correct 24 ms 17052 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16472 KB Output is correct
2 Correct 28 ms 16532 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20948 KB Output is correct
2 Correct 39 ms 21844 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 23532 KB Output is correct
2 Correct 51 ms 24148 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24544 KB Output is correct
2 Correct 58 ms 24660 KB Output is correct