Submission #249686

#	Time	Username	Problem	Language	Result	Execution time	Memory
249686		Mercenary	Pictionary (COCI18_pictionary)	C++14	140 / 140	123 ms	22848 KiB

pictionary

//how ? boruvska + lca

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int logn = log2(maxn) + 1;

int n , m , q;
vector<ii> adj[maxn];
int vis[maxn];
int lab[maxn];
int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
void Merge(int u , int v , int c){
    u = FindLab(u) , v = FindLab(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u , v);
    lab[u] += lab[v];lab[v] = u;
    adj[u].pb(mp(v,c));
    adj[v].pb(mp(u,c));
}

int M[maxn][logn] , P[maxn][logn];
int dep[maxn];

void dfs(int u , int par){
    for(auto & c : adj[u]){
        if(c.first == par)continue;
        M[c.first][0] = c.second;
        P[c.first][0] = u;
        dep[c.first] = dep[u] + 1;
        for(int i = 1 ; i < logn ; ++i){
            P[c.first][i] = P[P[c.first][i - 1]][i - 1];
            M[c.first][i] = max(M[c.first][i - 1] , M[P[c.first][i - 1]][i - 1]);
        }
        dfs(c.first , u);
    }
}

int getm(int u , int v){
    int res = 0;
    if(dep[u] < dep[v])swap(u , v);
    for(int i = 0 ; i < logn ; ++i){
        if((dep[u] - dep[v]) & (1 << i)){
            res = max(res , M[u][i]);
            u = P[u][i];
        }
    }
    if(u == v)return res;
    for(int i = logn - 1 ; i >= 0 ; --i){
        if(P[u][i] != P[v][i]){
            res = max(res , M[u][i]);
            res = max(res , M[v][i]);
            u = P[u][i];
            v = P[v][i];
        }
    }
    res = max(res , M[u][0]);
    res = max(res , M[v][0]);
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    memset(lab,-1,sizeof lab);
    cin >> n >> m >> q;
    for(int i = m ; i >= 1 ; --i){
        int a = -1 , b = -1;
        for(int j = i * 2 ; j <= n ; j += i){
            Merge(i,j,m+1-i);
        }
    }
    dfs(1,0);
    while(q--){
        int u , v;cin >> u >> v;
        cout << getm(u , v) << '\n';
    }
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:89:13: warning: unused variable 'a' [-Wunused-variable]
         int a = -1 , b = -1;
             ^
pictionary.cpp:89:22: warning: unused variable 'b' [-Wunused-variable]
         int a = -1 , b = -1;
                      ^
pictionary.cpp:83:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:84:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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