제출 #876974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876974		8pete8	자매 도시 (APIO20_swap)	C++14	100 / 100	308 ms	74884 KiB

swap

#include "swap.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ll long long    
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
const int mxn=3e5,lg=30;
int pa[mxn+10],deg[mxn+10],val[mxn+10],up[mxn+10][lg+5],h[mxn+10];
bool yes[mxn+10];
vector<int>adj[mxn+10];
bitset<mxn+10>vis;
int find(int u){return ((pa[u]==u)?u:pa[u]=find(pa[u]));}
int cnt=0;
void merg(int a,int b){
  int u=find(a),v=find(b);
  cnt++;
  if(u==v){
    yes[cnt]=true;
    adj[cnt].pb(v);
    pa[v]=cnt;
    return;
  }
  adj[cnt].pb(v);
  adj[cnt].pb(u);
  yes[cnt]=(yes[v]|yes[u]);
  deg[a]++,deg[b]++;
  if(deg[a]>=3||deg[b]>=3)yes[cnt]=true;
  pa[u]=pa[v]=cnt;
}
void dfs(int cur){
  if(vis[cur])return;
  vis[cur]=true;
  for(auto i:adj[cur])h[i]=h[cur]+1,up[i][0]=cur,dfs(i);
}
void init(int n,int m,vector<int>u,vector<int>v,vector<int>w){
  cnt=n-1;
  for(int i=0;i<=(n+m+1);i++)pa[i]=i;
  vector<ppii>e;
  for(int i=0;i<m;i++)e.pb({w[i],{u[i],v[i]}});
  sort(all(e));
  for(auto i:e)merg(i.s.f,i.s.s),val[cnt]=i.f;
  for(int i=0;i<=lg;i++)up[cnt][i]=cnt;
  dfs(cnt);
  for(int j=1;j<=lg;j++)for(int i=0;i<=cnt;i++)up[i][j]=up[up[i][j-1]][j-1];
}
int getMinimumFuelCapacity(int a,int b){
  if(h[a]<h[b])swap(a,b);
  int k=h[a]-h[b];
  for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
  if(a==b&&yes[a])return val[a];
  for(int i=lg;i>=0;i--)if((up[a][i]!=up[b][i])||(up[a][i]==up[b][i]&&!yes[up[a][i]]))a=up[a][i],b=up[b][i];
  if((up[a][0]==up[b][0])&&(yes[up[a][0]]))return val[up[a][0]];
  return -1;
}/*
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}*/

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