제출 #560304

#제출 시각아이디문제언어결과실행 시간메모리
560304TrungNotChung자매 도시 (APIO20_swap)C++11
0 / 100
2100 ms47604 KiB
//TrungNotChung #include <bits/stdc++.h> #define pii pair<int , int> #define fi first #define se second #define BIT(x,i) (1&((x)>>(i))) #define MASK(x) (1LL<<(x)) #define CNT(x) __builtin_popcountll(x) #define task "tnc" #include "swap.h" using namespace std; const int N = (int)1e5+228; const int M = (int)2e5+228; const int INF = (int)1e9+7; const int logn = 17; int n , m , par[N] , dad[N][logn+1] , b[N]; int h[N] , f[N][logn+1] , g[N][logn+1]; vector<pii> adj1[N] , adj2[N]; bool mark1[M] , mark2[N]; struct edge { int u , v , w; bool operator < (const edge &x) const { return w < x.w; } }edges[M]; struct DisjointSet { vector<int> lab; int n; DisjointSet(int _n = 0) { n = _n; lab.assign(n+7 , -1); } int Find(int u) { if(lab[u] < 0) return u; return lab[u] = Find(lab[u]); } bool join(int u , int v) { u = Find(u) , v = Find(v); if(u == v) return false; if(lab[u] < lab[v]) swap(u , v); lab[v] += lab[u] , lab[u] = v; return true; } }dsu; void dfs(int u , int prv) { b[u] = prv; if(u != 0) { for(int i=0 ; i<(int)adj2[par[u]].size() ; ++i) { int id = adj2[par[u]][i].se; if(id != b[par[u]] && id != prv) { f[u][0] = edges[id].w; break; } } } for(int j=1 ; j<=logn ; ++j) { f[u][j] = min(f[u][j-1] , f[dad[u][j-1]][j-1]); } for(int i=0 ; i<(int)adj1[u].size() ; ++i) { int v = adj1[u][i].fi , id = adj1[u][i].se; if(id == prv || v == par[u]) continue; par[v] = u , h[v] = h[u] + 1 , dad[v][0] = u , g[v][0] = edges[id].w; for(int j=1 ; j<=logn ; ++j) { dad[v][j] = dad[dad[v][j-1]][j-1]; g[v][j] = max(g[v][j-1] , g[dad[v][j-1]][j-1]); } dfs(v , id); } } 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) edges[i].u = U[i] , edges[i].v = V[i] , edges[i].w = W[i]; sort(edges , edges+m); dsu = DisjointSet(n); for(int i=0 ; i<m ; ++i) { int u = edges[i].u , v = edges[i].v; adj2[u].push_back(make_pair(v , i)); adj2[v].push_back(make_pair(u , i)); if(dsu.join(u , v)) { adj1[u].push_back(make_pair(v , i)); adj1[v].push_back(make_pair(u , i)); } } memset(f , 0x3f , sizeof(f)); h[0] = 1; dfs(0 , -1); // for(int i=0 ; i<m ; ++i) cout << edges[i].w << " "; // cout << '\n'; } int getMin(int u , int v) { int x = u , y = v; for(int i=0 ; i<m ; ++i) mark1[i] = false; for(int i=0 ; i<n ; ++i) mark2[i] = false; if(h[u] < h[v]) swap(u , v); while(h[u] > h[v]) { mark2[u] = true; mark1[b[u]] = true; u = par[u]; } while(u != v) { mark2[u] = mark2[v] = true; mark1[b[u]] = mark1[b[v]] = true; u = par[u] , v = par[v]; } mark2[u] = true; for(int i=0 ; i<m ; ++i) { if(mark1[i]) continue; if(mark2[edges[i].u] && edges[i].u != x && edges[i].u != y) return edges[i].w; if(mark2[edges[i].v] && edges[i].v != x && edges[i].v != y) return edges[i].w; } return INF; } int getMax(int u , int v) { int res = 0; if(h[u] < h[v]) swap(u , v); for(int i=logn ; i>=0 ; --i) { if(h[dad[u][i]] >= h[v]) { res = max(res , g[u][i]); u = dad[u][i]; } } if(u == v) return res; for(int i=logn ; i>=0 ; --i) { if(dad[u][i] != dad[v][i]) { res = max(res , max(g[u][i] , g[v][i])); u = dad[u][i] , v = dad[v][i]; } } res = max(res , max(g[u][0] , g[v][0])); return res; } vector<int> adj3[N]; int low[N] , num[N] , inID[N] , t , cur; stack<int> st; void tarjan(int u , int p) { low[u] = num[u] = ++t; st.push(u); for(int v : adj3[u]) { if(v == p) continue; if(num[v]) low[u] = min(low[u] , num[v]); else { tarjan(v , u); low[u] = min(low[u] , low[v]); } } if(low[u] == num[u]) { ++cur; int v; do { v = st.top(); st.pop(); inID[v] = cur; low[v] = num[v] = INF; } while(u != v); } } bool check(int mid , int X , int Y) { for(int i=0 ; i<n ; ++i) adj3[i].clear() , low[i] = num[i] = inID[i] = 0; t = 0 , cur = 0; for(int i=0 ; i<=mid ; ++i) { int u = edges[i].u , v = edges[i].v; adj3[u].push_back(v) , adj3[v].push_back(u); } for(int i=0 ; i<n ; ++i) if(!num[i]) tarjan(i , -1); return (inID[X] == inID[Y]); } int getMinimumFuelCapacity(int X, int Y) { int tmp1 = getMin(X , Y) , tmp2 = getMax(X , Y); int res = max(tmp1 , tmp2); if(m == n-1) { if(res >= INF) return -1; return res; } int l = 0 , r = m-1 , tmp3 = INF; while(l <= r) { int mid = (l+r)/2; if(check(mid , X , Y)) { tmp3 = edges[mid].w; r = mid-1; } else l = mid+1; } res = min(res , tmp3); if(res >= INF) return -1; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...