Submission #487813

#	Time	Username	Problem	Language	Result	Execution time	Memory
487813		nickmet2004	Swapping Cities (APIO20_swap)	C++11	0 / 100	3 ms	5076 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"

using namespace std;
const int N = 2e5 + 5;
int n , m;
vector<pair<int, int>> adj[N];
int P[N][20] , mn[N][22] , depth[N] , dp[N][22];
void dfs(int u , int p = -1){
    P[u][0] = p;
    for(int i = 1;i <= 17; ++i) P[u][i] = P[P[u][i- 1]][i -1] , mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]);
    for(auto x : adj[u]){
        int v = x.first , w= x.second;
        if(v == p)continue;
        mn[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v , u);
    }
}
void Q(int u, int p = -1){
    for(auto x : adj[u]){
        int v= x.first , w = x.second;
        if(v==p)continue;
        Q(v , u);
    }
    if(p==-1)return;
    for(auto x : adj[p]) if(x.first != u)dp[u][0] = min(dp[u][0] , x.second);
    for(int i =1; i <= 20; ++i) dp[u][i] = min(dp[u][i - 1] , dp[P[u][i - 1]][i - 1]);
}
int MN = 2e9 , Y = 2e9;
void LCA(int u , int v){
    if(depth[u] < depth[v])swap(u , v);
    int k = depth[u] - depth[v];
    for(int i = 17; ~i; --i){
        if(k>>i & 1)MN = min(MN , mn[u][i]) , Y = min(Y , dp[u][i]) ,u= P[u][i];
    }
    return;
    for(int i = 17; ~i; --i){
        if(P[u][i] != P[v][i]){
            MN = min({MN , mn[u][i] , mn[v][i]});
            Y = min({Y , dp[u][i] , dp[v][i]});
            u =P[u][i] , v= P[v][i];
        }
    }
    Y = min({Y , dp[u][0] , dp[v][0]});
    MN = min({MN ,mn[u][0] , mn[v][0]});
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W){
    n = N, m = M;
    for(int i = 1; i <= m; ++i){
        adj[U[i-1]].emplace_back(V[i - 1] , W[i - 1]);
        adj[V[i -1]].emplace_back(U[i - 1] ,W[i - 1]);
    }
    for(int i= 1; i<= n; ++i)for(int j =0; j <= 20; ++j) dp[i][j] = mn[i][j] = 2e9;
    dfs(1);
    Q(1);
}
int getMinimumFuelCapacity(int u, int v) {
	LCA(u , v);
	if(Y == 2e9)return -1;
	else return max(Y , MN);
}
/*
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u , v , w;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> w;
        adj[u].emplace_back(v , w);
        adj[v].emplace_back(u ,w);
    }
    for(int i= 1; i<= n; ++i)for(int j =0; j <= 20; ++j) dp[i][j] = mn[i][j] = 2e9;
    dfs(1);
    Q(1);

}
*/

Compilation message (stderr)

swap.cpp: In function 'void Q(int, int)':
swap.cpp:22:26: warning: unused variable 'w' [-Wunused-variable]
   22 |         int v= x.first , w = x.second;
      |                          ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27