Submission #1126758

#TimeUsernameProblemLanguageResultExecution timeMemory
1126758InvMODSwapping Cities (APIO20_swap)C++20
0 / 100
551 ms589824 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define gcd __gcd #define sz(v) (int) v.size() #define pb push_back #define pi pair<int,int> #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define REV(i, a, b) for(int i = (a); i >= (b); i--) #define dbg(x) "[" #x " = " << (x) << "]" ///#define int long long using ll = long long; using ld = long double; using ull = unsigned long long; template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;} template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;} const int N = 3e5+5; const int lg = 18; int h[N], timerDFS, tin[N], tout[N], value[N], par[lg][N]; bool can[N], passable[lg][N]; vector<int> adj[N]; namespace dsu{ vector<int> dsu, sz, sumDeg, deg; int node = 0; int f(int x){ if(x == dsu[x]) return x; return dsu[x] = f(dsu[x]); } void addEdge(int u, int v, int w){ int fau = f(u), fav = f(v); deg[u]++, deg[v]++; dsu[++node] = node; dsu[fau] = dsu[fav] = node; if(fau != fav){ sumDeg[node] = sumDeg[fau] + sumDeg[fav] + 2; sz[node] = sz[fau] + sz[fav]; adj[node].push_back(fau); adj[node].push_back(fav); } else{ sumDeg[node] = sumDeg[fau] + 2; sz[node] = sz[fau]; adj[node].push_back(fau); } can[node] |= (deg[u] > 2 || deg[v] > 2); can[node] |= (can[fau] || can[fav]); can[node] |= (sumDeg[node] >= sz[node] * 2); value[node] = w; return; } void build(int n){ sz.resize(n + 1), deg.resize(n + 1); dsu.resize(n + 1), sumDeg.resize(n + 1); for(int i = 1; i <= n; i++){ dsu[i] = i; sumDeg[i] = 0, sz[i] = 1; } node = n; return; } } void preDFS(int x){ tin[x] = ++timerDFS; for(int v : adj[x]){ par[0][v] = x; passable[0][v] = can[x]; for(int i = 1; i < lg; i++){ par[i][v] = par[i - 1][par[i - 1][v]]; passable[i][v] = (passable[i - 1][v] | passable[i - 1][par[i - 1][v]]); } h[v] = h[x] + 1; preDFS(v); } tout[x] = timerDFS; return; } bool inSub(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; } int get_LCA(int u, int v){ if(inSub(u, v)) return u; if(inSub(v, u)) return v; for(int i = lg - 1; i >= 0; i--){ if(par[i][u] > 0 && !inSub(par[i][u], v)){ u = par[i][u]; } } return par[0][u]; } int findPass(int u){ if(can[u]) return u; for(int i = lg - 1; i >= 0; i--){ if(par[i][u] > 0 && !passable[i][u]){ u = par[i][u]; } } return par[0][u]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){ vector<int> id(M); iota(all(id), 0); sort(all(id), [&](int x, int y){return W[x] < W[y];}); dsu::build(N); for(int i = 0; i < sz(id); i++){ int eid = id[i]; U[eid]++, V[eid]++; dsu::addEdge(U[eid], V[eid], W[eid]); } // LCA and check Comp ? for(int i = 1; i <= dsu::node; i++){ if(i == dsu::f(i)){ preDFS(i); } } return; } int getMinimumFuelCapacity(int X, int Y){ if(dsu::f(++X) != dsu::f(++Y)) return -1; int lca = get_LCA(X, Y); int nearPass = findPass(lca); return nearPass > 0 ? value[nearPass] : -1; } //#define name "InvMOD" #ifdef name signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(name".INP", "r")){ freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout); } int n,m; cin >> n >> m; vector<vector<int>> a(3, vector<int>(m)); FOR(i, 0, 2){ FOR(j, 0, m - 1){ cin >> a[i][j]; } } init(n, m, a[0], a[1], a[2]); int q; cin >> q; vector<vector<int>> Q(2, vector<int>(q + 1)); FOR(i, 0, 1){ FOR(j, 1, q){ cin >> Q[i][j]; } } FOR(i, 1, q){ cout << getMinimumFuelCapacity(Q[0][i], Q[1][i]) <<"\n"; } return 0; } #endif // name /* Test case 1: 5 6 0 0 1 1 1 2 1 2 2 3 4 3 4 4 1 2 10 3 3 1 2 0 2 4 1 */ /* Test case 2: 3 2 0 0 1 2 5 5 1 1 2 */
#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...