oj.uz

Submission #708826

# Submission time Handle Problem Language Result Execution time Memory
708826 2023-03-12T11:59:51 Z Hacv16 Pictionary (COCI18_pictionary) C++17
140 / 140
 179 ms 41860 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5168 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5204 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5488 KB Output is correct
2 Correct 23 ms 5460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5804 KB Output is correct
2 Correct 29 ms 5708 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12884 KB Output is correct
2 Correct 35 ms 12884 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16172 KB Output is correct
2 Correct 65 ms 17804 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 21424 KB Output is correct
2 Correct 74 ms 22528 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 27584 KB Output is correct
2 Correct 116 ms 30372 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 33492 KB Output is correct
2 Correct 154 ms 37688 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 41828 KB Output is correct
2 Correct 172 ms 41860 KB Output is correct