이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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+100,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++;
adj[cnt].pb(v);
if(u==v){
yes[cnt]=true;
pa[v]=cnt;
return;
}
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<mxn;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 lca(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)return a;
for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
return up[a][0];
}
int getMinimumFuelCapacity(int a,int b){
int node=lca(a,b);
for(int i=lg;i>=0;i--)if(!yes[up[node][i]])node=up[node][i];
if(!yes[node])node=up[node][0];
if(yes[node])return val[node];
else 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;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |