Submission #708826

#	Time	Username	Problem	Language	Result	Execution time	Memory
708826		Hacv16	Pictionary (COCI18_pictionary)	C++17	140 / 140	179 ms	41860 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 2e5 + 15;
const int LOG = 24;
const int INF = 0x3f3f3f3f;
 
int n, m, q, pai[MAX], sze[MAX], dp[MAX][LOG], low[MAX][LOG], depth[MAX];
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> adj[MAX];
 
int find(int u){ 
    return pai[u] = (pai[u] == u ? u : find(pai[u]));
}
 
bool join(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return false;
 
    if(sze[v] > sze[u]) swap(u, v);
    pai[v] = u; sze[u] += sze[v]; 
    
    return true;
}
 
void dfs(int u, int p, int d, int wg){
    depth[u] = d; dp[u][0] = p; low[u][0] = wg;
    
    for(auto [v, w] : adj[u]){
        if(v == p) continue;
        dfs(v, u, d + 1, w);
    }
}
 
int query(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    
    int ans = INF, k = depth[u] - depth[v];
    
    for(int i = LOG - 1; i >= 0; i--)
        if(k & (1 << i)){ ans = min(ans, low[u][i]); u = dp[u][i]; }
        
    if(u == v) return ans;
    
    for(int i = LOG - 1; i >= 0; i--){
        if(dp[u][i] != dp[v][i]){
            ans = min({ ans, low[u][i], low[v][i] });
            u = dp[u][i]; v = dp[v][i];
        }
    }
    
    ans = min(ans, low[u][0]);
    ans = min(ans, low[v][0]);
 
    return ans;
}
 
int32_t main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m >> q;
 
    for(int i = 1; i <= n; i++){
        for(int j = i + i; j <= n; j += i)
            edges.emplace_back(i, i, j);
        
        pai[i] = i; sze[i] = 1;
    }
 
    sort(edges.begin(), edges.end(), greater<tuple<int, int, int>>());
 
    for(auto [w, u, v] : edges){
        if(w > m) continue;
        
        if(join(u, v)){
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }
    }
    
    dfs(1, 1, 1, INF);
    
    for(int j = 1; j < LOG; j++){
        for(int i = 1; i <= n; i++){
            dp[i][j] = dp[ dp[i][j - 1] ][j - 1];
            low[i][j] = min(low[i][j - 1], low[ dp[i][j - 1] ][ j - 1 ]);
        }
    }
    
    while(q--){
        int u, v; cin >> u >> v;
        cout << m - query(u, v) + 1 << '\n';
    }
}

• 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