Submission #1233509

#TimeUsernameProblemLanguageResultExecution timeMemory
1233509thelegendary08Swapping Cities (APIO20_swap)C++17
7 / 100
90 ms18892 KiB
#include "swap.h" #include<bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define f0r(i,n) for(signed i = 0; i<n; i++) #define FOR(i, k, n) for(signed i = k; i<n; i++) #define vi vector<int> #define vpii vector<pair<int,int>> #define pii pair<int,int> #define vb vector<bool> #define mii map<int,int> #define vvi vector<vector<int>> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl; #define dout(a) cout<<a<<' '<<#a<<endl; #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl; using namespace std; struct edge{ int u, v, w; }; vector<vpii> adj; int n,m; vector<vi>edges; struct DSU{ int n; vi par, sz, hasthree, hascyc; DSU(int N){ n = N; par.resize(n); sz.resize(n); hasthree.resize(n); hascyc.resize(n); f0r(i,n){ par[i] = i; sz[i] = 1; hasthree[i] = 0; hascyc[i] = 0; } } int find(int x){ while(x != par[x])x = par[x]; return x; } void unite(int a, int b){ // dout2(a,b); a = find(a); b = find(b); if(a == b){ hascyc[a] = 1; return; } if(sz[a] < sz[b])swap(a,b); sz[a] += sz[b]; par[b] = a; hascyc[a] |= hascyc[b]; hasthree[a] |= hasthree[b]; } }; vi dist; int l2; void init(signed N, signed M, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) { n = N; m = M; adj.resize(N); dist.resize(n); dist[0] = 4e18; f0r(i, M){ edges.pb({W[i], U[i], V[i]}); adj[U[i]].pb(mp(V[i], W[i])); adj[V[i]].pb(mp(U[i], W[i])); dist[V[i]] = W[i]; } sort(edges.begin(), edges.end()); vi d = dist; sort(d.begin(), d.end()); l2 = d[2]; } signed getMinimumFuelCapacity(signed X, signed Y) { if(n <= 3)return -1; if(X > Y)swap(X,Y); if(X == 0){ return max(dist[Y], l2); } else{ return max({dist[X], dist[Y], l2}); } /* vi deg(n); DSU d = DSU(n); f0r(i, m){ d.unite(edges[i][1], edges[i][2]); deg[edges[i][1]]++; deg[edges[i][2]]++; int x = d.find(X); int y = d.find(Y); if(deg[edges[i][1]] == 3){ d.hasthree[d.find(edges[i][1])] = 1; } if(deg[edges[i][2]] == 3){ d.hasthree[d.find(edges[i][2])] = 1; } if(x == y && (d.hasthree[x] || d.hascyc[x])){ return edges[i][0]; } } return -1; */ }
#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...