제출 #532890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532890		ohohorz	자매 도시 (APIO20_swap)	C++14	0 / 100	1594 ms	524292 KiB

swap

#include "swap.h"

#include <vector>
#include<set>
#include<algorithm>
#include<climits>
#include<map>
using namespace std;

// #define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define sz(x) (int)x.size()

const int MAXN = 1e5 + 5;
const int INF = INT_MAX;
const int LOGN = 22;

int n, m;
vector< pair <int,int> > g[MAXN];
int up[MAXN][LOGN], mx[MAXN][LOGN], aux[MAXN][LOGN], tin[MAXN], tout[MAXN], timer, dist[MAXN], child[MAXN], par[MAXN];
map<pii,int> wt;

void dfs(int u,int p = 0,int d = 0){
    up[u][0] = p;
    tin[u] = ++timer;
    if(p != 0) child[p] = u;
    par[u] = p;
    dist[u] = d;
    if(p > 0) mx[u][0] = wt[mp(u, p)];
    for(int i = 0;i < sz(g[u]);i++){
        int v = g[u][i].first;
        if(v != p) dfs(v, u, d + 1);
    }
    tout[u] = timer;
}

bool is_ans(int u,int v){
    return (tin[u] <= tin[v] and tout[u] >= tout[v]);
}
int LCA(int u,int v){
    if(is_ans(u, v)) return u;
    if(is_ans(v, u)) return v;
    for(int i = 21;i >= 0;i--){
        if(!is_ans(up[u][i], v)) 
            u = up[u][i];
    }
    return up[u][0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N,m = M;
  for(int i = 0;i < m;i++){
    int u = U[i] + 1;
    int v = V[i] + 1;
    g[u].pb(mp(v, W[i]));
    g[v].pb(mp(u, W[i]));
    wt[mp(u, v)] = W[i];
    wt[mp(v, u)] = W[i];
  }
  dfs(1);
  for(int i =1;i<=n;i++){
      if(child[i] == 0) continue;
      aux[child[i]][0] = INF;
      for(auto p:g[i]){
          int j = p.first;
          int w = p.second;
          if(j != child[i] and j!=par[i])
            aux[child[i]][0] = min(aux[child[i]][0], w);
      }
  }
  for(int j = 1;j < 22;j++){
      for(int i = 1;i<=n;i++){
          up[i][j] = up[up[i][j-1]][j-1];
          mx[i][j] = max(mx[i][j-1], mx[up[i][j-1]][j-1]);
          aux[i][j] = min(aux[i][j-1], aux[up[i][j-1]][j-1]);
      
    }
  }
  
  
}

int getMinimumFuelCapacity(int X, int Y) {
  X++, Y++;
  int lca = LCA(X, Y);
  int x = X;
  int cur = 0;
  int mn =INF;
  for(int i = 21;i >= 0;i--){
      if(dist[lca]<dist[up[x][i]]){
          cur = max(cur, mx[x][i]);
          mn = min(mn, aux[x][i]);
          x = up[x][i];

      }
  }
  int y = Y;
  for(int i = 21;i >= 0;i--){
      if(dist[lca]<dist[up[y][i]]){
          cur = max(cur, mx[y][i]);
          mn = min(mn, aux[y][i]);
          y = up[y][i];
      }
  }
  if(mn == INF) return -1;
  return max(mn, cur);
}

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