Submission #1200645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200645		Mohamed_Kachef06	자매 도시 (APIO20_swap)	C++17	0 / 100	144 ms	22344 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
#define all(x) x.begin() , x.end()

int n , m;
vector<int> u , v , w;
int mx = 0; 

struct LCA{
  vector<int> anc[20] , dep; 
  void init(vector<vector<int>> &adj , int n){
    for (auto &j : anc) j.resize(n); 
    dep.resize(n); 
    dfs(0 , -1 , adj); 
  }
  void dfs(int node , int par , vector<vector<int>> &adj){
    for (auto i : adj[node]){
      if (i == par) continue; 
      dep[i] = dep[node] + 1; 
      anc[0][i] = node; 
      for (int j = 1 ; j < 20 ; j++){
        anc[j][i] = anc[j-1][anc[j-1][i]]; 
      }
      dfs(i , node , adj); 
    }
  }
  int jump(int u , int k){
    for (int j = 19 ; j >= 0 ; j--){
      if (k & (1<<j)) u = anc[j][u]; 
    }
    return u; 
  }
  int lca(int u , int v){
    if (dep[u] > dep[v]) swap(u , v); 
    v = jump(v , dep[v] - dep[u]); 
    if (u == v) return u; 
    for (int j = 19 ; j >= 0 ; j--){
      if (anc[j][u] != anc[j][v]) u = anc[j][u], v = anc[j][v]; 
    }
    return anc[0][u]; 
  }
};

  LCA l; 


void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
  n = N  , m = M , u = U , V = v , w = W; 
  if (m != n-1) return; 
  vector<vector<int>> adj(N); 
  for (int i = 0 ; i < M ; i++) adj[U[i]].push_back(V[i]),adj[V[i]].push_back(U[i]); 
  l.init(adj , N); 
}

int getMinimumFuelCapacity(int X, int Y) {
  if (m != n-1) return -1; 
  int c = l.lca(X , Y); 
  if (c != X && c != Y && l.dep[c]) return 0;
  else return -1;  
}

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