oj.uz

Submission #708822

# Submission time Handle Problem Language Result Execution time Memory
708822 2023-03-12T11:55:17 Z Hacv16 Pictionary (COCI18_pictionary) C++17
84 / 140
 105 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 2e6 + 15;
const int LOG = 25;
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; 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 27 ms 47444 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 48404 KB Output is correct
2 Correct 52 ms 48412 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 48920 KB Output is correct
2 Correct 59 ms 48688 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 56112 KB Output is correct
2 Correct 58 ms 56068 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 59736 KB Output is correct
2 Correct 96 ms 61336 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 65480 KB Output is correct
2 Runtime error 87 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -