Submission #227572

#	Time	Username	Problem	Language	Result	Execution time	Memory
227572		mohamedsobhi777	Pictionary (COCI18_pictionary)	C++14	140 / 140	301 ms	27852 KiB

pictionary

#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 (stderr)

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 / 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