oj.uz

Submission #748752

# Submission time Handle Problem Language Result Execution time Memory
748752 2023-05-26T21:28:07 Z ETheBest3 Pictionary (COCI18_pictionary) C++14
140 / 140
 119 ms 49764 KB 
#include<bits/stdc++.h>
#define lli long long
#define endl "\n"
using namespace std;
const lli MAXN=100005, LOGN=25, INF=999999999;
lli N, M, Q, par[MAXN], sz[MAXN], dep[MAXN], ti[MAXN], up[LOGN+1][MAXN];
lli koren, maxx[LOGN+1][MAXN], a, b;
vector<lli> v[MAXN];
void add_node(lli x){
    par[x]=x;
    sz[x]=1;
    ti[x]=x;
    return;
}
lli find_parent(lli x){
    if(par[x]==x)return x;
    return find_parent(par[x]);
}
void merge_v(lli x, lli y){
    lli rootx=find_parent(x), rooty=find_parent(y);
    if(rootx==rooty)return;
    if(sz[rootx]<=sz[rooty]){
        par[rootx]=rooty;
        sz[rooty]+=sz[rootx];
        ti[rootx]=min(x, y);
    }else{
        par[rooty]=rootx;
        sz[rootx]+=sz[rooty];
        ti[rooty]=min(x, y);
    }
    return;
}
void dfs(lli x){    
    for(lli i=0; i<v[x].size(); i++){
        dep[v[x][i]]=dep[x]+1;
        dfs(v[x][i]);
    }
    return;
}
lli lca(lli x, lli y){
    if(dep[x]<dep[y])swap(x, y);
    lli ans=INF;
    for(lli i=LOGN; i>=0; i--){
        if(dep[x]-(1<<i)>=dep[y]){
            ans=min(ans, maxx[i][x]);
            x=up[i][x];
        }
    }
    if(x==y)return ans;
    for(lli i=LOGN; i>=0; i--){
        if(up[i][x]!=up[i][y]){
            ans=min(ans, maxx[i][x]);
            ans=min(ans, maxx[i][y]);
            x=up[i][x];
            y=up[i][y];
        }
    }
    ans=min(ans, maxx[0][x]);
    ans=min(ans, maxx[0][y]);
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for(lli i=1; i<=N; i++)add_node(i);
    for(lli i=M; i>0; i--){
        for(lli j=2*i; j<=N; j+=i){
            merge_v(i, j);
        }
    }
    for(lli i=1; i<=N; i++){
        up[0][i]=par[i];
        maxx[0][i]=ti[i];
        if(par[i]==i)koren=i;
        else v[par[i]].push_back(i);
    }
    dep[koren]=1;
    dfs(koren);
    for(lli st=1; st<=LOGN; st++){
        for(lli i=1; i<=N; i++){
            up[st][i]=up[st-1][up[st-1][i]];
            maxx[st][i]=min(maxx[st-1][i], maxx[st-1][up[st-1][i]]);
        }
    }
    bool fl=0;
    for(lli q=0; q<Q; q++){
        cin>>a>>b;
        cout<<M-lca(a, b)+1<<endl;
    }
    return 0;
}

Compilation message

pictionary.cpp: In function 'void dfs(long long int)':
pictionary.cpp:34:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(lli i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:87:10: warning: unused variable 'fl' [-Wunused-variable]
   87 |     bool fl=0;
      |          ^~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3448 KB Output is correct
2 Correct 25 ms 4088 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3836 KB Output is correct
2 Correct 27 ms 4464 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13260 KB Output is correct
2 Correct 28 ms 13644 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17492 KB Output is correct
2 Correct 47 ms 19656 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23964 KB Output is correct
2 Correct 51 ms 25932 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30808 KB Output is correct
2 Correct 100 ms 34884 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 38768 KB Output is correct
2 Correct 102 ms 44576 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 48672 KB Output is correct
2 Correct 119 ms 49764 KB Output is correct