| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1066661 | SoMotThanhXuan | 자매 도시 (APIO20_swap) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <swap.h>
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = b; i >= a; --i)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define REPD(i, a, b) for(int i = b; i > a; -- i)
#define ALL(v) v.begin(),v.end()
#define next __next
#define left __left
#define right __right
#define prev __prev
const int MOD[6] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277, 998244353};
const int BASE[6] = {23309, 300, 330, 280, 2309, 256};
const int base = BASE[0];
const int mod = MOD[0];
void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
void minimize(int &u, int v){
if(u > v) u = v;
}
void maximize(int &u, int v){
if(u < v) u = v;
}
void minimizell(long long &u, long long v){
if(u > v) u = v;
}
void maximizell(long long &u, long long v){
if(u < v) u = v;
}
const int maxN = 3e5 + 2;
const int maxM = 3e5 + 2;
const int maxK = 1e2 + 2;
const int INF = 1e9 + 8;
const long long INFLL = 1e18;
const int LOG = 16;
vector<pair<int, int>> adj[maxN];
int next[maxN];
bool cycle[maxN];
pair<int, pair<int, int>> edge[maxM];
int n;
int root[maxN], high[maxN];
int par[LOG + 1][maxN], Max[LOG + 1][maxN], child[maxN];
int find_root(int v){
return root[v] = root[v] == v ? v : find_root(root[v]);
}
void dfs(int u, int p){
for(pair<int, int> x : adj[u]){
int v = x.first;
int w = x.second;
if(v == p)continue;
high[v] = high[u] + 1;
// cout << u << ' ' << v << "\n";
dfs(v, u);
++child[u];
par[0][v] = u;
Max[0][v] = w;
}
}
void dfs2(int u, int p){
if(p){
if(child[p] == 1){
next[u] = Max[0][u];
}else next[u] = next[p];
}
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p)dfs2(v, u);
}
}
void dfs3(int u, int p){
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
dfs3(v, u);
cycle[u] |= cycle[v];
}
}
}
void sparse_table(){
}
void addEdge(int u, int v, int w){
++n;
u = find_root(u);
v = find_root(v);
root[n] = n;
root[u] = root[v] = n;
adj[n].push_back({u, w});
// cout << n << ' ' << u << ' ' << v << "\n";
if(u != v)adj[n].push_back({v, w});
}
void init(int N, int M, int U[], int V[], int W[]){
REP(i, 0, M){
edge[i + 1] = {W[i], {U[i] + 1, V[i] + 1}};
}
sort(edge + 1, edge + 1 + M);
n = N;
FOR(i, 1, M)addEdge(edge[i].se.fi, edge[i].se.se, edge[i].fi);
dfs(n, 0);
high[0] = -1;
FOR(i, 1, N)root[i] = i;
FOR(j, 1, LOG)FOR(i, 1, n){
par[j][i] = par[j - 1][par[j - 1][i]];
Max[j][i] = max(Max[j - 1][i], Max[j - 1][par[j - 1][i]]);
}
dfs2(n, 0);
// FOR(i, 1, n)cout << child[i] << ' ';cout << "\n";
FOR(i, N + 1, n)if(child[i] == 1)cycle[i] = true;
dfs3(n, 0);
// FOR(i, 1, n)cout << next[i] << ' ';cout << "\n";
// FOR(i, 1, n)cout << cycle[i] << ' ';cout << "\n";
}
int getMinimumFuelCapacity(int u, int v){
int res = 0;
if(high[u] < high[v]) swap(u, v);
FORD(i, 0, LOG)if(high[par[i][u]] >= high[v])maximize(res, Max[i][u]),u = par[i][u];
if(u == v){
if(cycle[u]) return res;
return next[u] == 0 ? -1 : next[u];
}
FORD(i, 0, LOG)if(par[i][u] != par[i][v]){
maximize(res, Max[i][u]);
maximize(res, Max[i][v]);
u = par[i][u];
v = par[i][v];
}
maximize(res, Max[0][u]);
maximize(res, Max[0][v]);
u = par[0][u];
if(cycle[u]){
return res;
}
else return next[u] == 0 ? - 1 : next[u];
}