제출 #1199756

#제출 시각아이디문제언어결과실행 시간메모리
1199756yeediot자매 도시 (APIO20_swap)C++20
100 / 100
157 ms45116 KiB
#ifndef local #include "swap.h" #endif #include<bits/stdc++.h> using namespace std; #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define __lg(x) 63-__builtin_clzll(x) const int mxn = 3e5 + 5; int n, m, ty[mxn], cnt, val[mxn], jump[20][mxn], nxt[mxn], dep[mxn]; vector<int>adj[mxn]; struct DSU{ int to[mxn], num[mxn], f[mxn], s[mxn]; void init(){ for(int i = 0; i < mxn; i++){ to[i] = f[i] = s[i] = i; ty[i] = 0; num[i] = 1; } } int find(int x){ return x == to[x] ? x : to[x] = find(to[x]); } void add_edge(int x, int y){ adj[x].pb(y); to[y] = x; } void merge(int x, int y, int c){ int ox = x, oy = y; x = find(x), y = find(y); if(x == y){ if(ty[x] == 0){ cnt++; add_edge(cnt, x); val[cnt] = c; ty[cnt] = 1; } else{ } } else{ cnt++; add_edge(cnt, x); add_edge(cnt, y); val[cnt] = c; if(ty[x] == 0 and ty[y] == 0){ ty[cnt] = 1 - ((ox == f[x] or ox == s[x]) and (oy == f[y] or oy == s[y])); f[cnt] = f[x] ^ s[x] ^ ox; s[cnt] = f[y] ^ s[y] ^ oy; } else{ ty[cnt] = 1; } } } }d; void dfs(int v, int pa){ jump[0][v] = pa; nxt[v] = nxt[pa]; dep[v] = dep[pa] + 1; if(ty[v] == 1) nxt[v] = v; for(auto u : adj[v]){ dfs(u, v); } } int lca(int a, int b){ if(dep[a] < dep[b]) swap(a, b); int dif = dep[a] - dep[b]; for(int i = 19; i >= 0; i--){ if(dif >> i & 1) a = jump[i][a]; } if(a == b) return nxt[a]; for(int i = 19; i >= 0; i--){ if(jump[i][a] != jump[i][b]){ a = jump[i][a], b = jump[i][b]; } } return nxt[jump[0][a]]; } void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N, m = M; d.init(); vector<array<int, 3>>edges; for(int i = 0; i < m; i++) edges.pb({W[i], U[i] + 1, V[i] + 1}); sort(all(edges)); cnt = n; for(auto [c, a, b] : edges) d.merge(a, b, c); dfs(cnt, cnt); for(int i = 1; i < 20; i++){ for(int j = 1; j <= cnt; j++){ jump[i][j] = jump[i - 1][jump[i - 1][j]]; } } } int getMinimumFuelCapacity(int X, int Y) { X++, Y++; int lc = lca(X, Y); if(lc == 0) return -1; else return val[lc]; return 0; } #ifdef local int main() { freopen("/Users/iantsai/cpp/input.txt","r",stdin); freopen("/Users/iantsai/cpp/output.txt","w",stdout); 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; } #endif
#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...