oj.uz

Submission #227572

# Submission time Handle Problem Language Result Execution time Memory
227572 2020-04-27T21:17:37 Z mohamedsobhi777 Pictionary (COCI18_pictionary) C++14
140 / 140
 301 ms 27852 KB 
#include<bits/stdc++.h>

using namespace std ; 

const int N = 1e5 + 7 ; 

int n , m , k ; 
int A[N] , B[N] ; 
int ans[N] , vis[N]; 

vector<int> qrs[N] , tree[N] ; 
map<pair<int , int > , int> anss ; 

struct DSU{
    vector<int> fat ; 
    bool build = 0 ; 
    void init(int n , bool ok = 0){
        fat.resize(n) ; 
        build = ok ; 
        for(int i = 0 ; i < n; i++){
            fat[i] = i ;
        }
    }
    int fin(int x){
        return fat[x] = (fat[x]==x?x:fin(fat[x]));
    }    
    void unio(int a , int b){
        int aa = fin(a) ; 
        int bb = fin(b) ; 
        if(aa!=bb){
            fat[aa] = bb ; 
            if(build){
                tree[aa].push_back(bb) ; 
                tree[bb].push_back(aa) ;                 
            }
        }
    }
} d , lca;

int dfs(int x , int p){
    vis[x] =1 ; 
    for(auto u : qrs[x]){
        if(vis[u]){
            anss[{x , u}] = anss[{u , x}] = lca.fin(u) ; 
        }
    }
    for(auto u : tree[x]){
        if(u==p)continue ; 
        dfs(u , x) ;
        lca.unio(u , x) ; 
    }
}

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    cin>>n>>m>>k ; 
    d.init(n+7 ,1 ) ; 
    lca.init(n+7) ; 
    for(int i =0 ; i < k ;i++){
        int l , r; 
        cin>>A[i] >>B[i] ; 
        qrs[A[i]].push_back(B[i]) ; 
        qrs[B[i]].push_back(A[i]) ; 
    }
    for(int i =m ; i ;i--){
        for(int j = i  + i ;j <=n ;j+=i){
            d.unio(j , i) ; 
        }
    }
    dfs(1 , 1) ; 
    for(int i = 0 ;i < k ;i++){
        cout<< m - anss[{A[i] , B[i]}] +1 <<"\n" ; 
    }
    return 0 ; 
}

Compilation message

pictionary.cpp: In function 'int dfs(int, int)':
pictionary.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
pictionary.cpp: In function 'int main()':
pictionary.cpp:61:13: warning: unused variable 'l' [-Wunused-variable]
         int l , r; 
             ^
pictionary.cpp:61:17: warning: unused variable 'r' [-Wunused-variable]
         int l , r; 
                 ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6016 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8064 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 15608 KB Output is correct
2 Correct 120 ms 16124 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 20684 KB Output is correct
2 Correct 218 ms 19192 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13688 KB Output is correct
2 Correct 90 ms 13688 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 14840 KB Output is correct
2 Correct 111 ms 15644 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 18808 KB Output is correct
2 Correct 127 ms 15736 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 22752 KB Output is correct
2 Correct 224 ms 22848 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 24568 KB Output is correct
2 Correct 240 ms 25340 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 27852 KB Output is correct
2 Correct 274 ms 27640 KB Output is correct