Submission #1233365

#TimeUsernameProblemLanguageResultExecution timeMemory
1233365clemmy14Swapping Cities (APIO20_swap)C++20
0 / 100
0 ms324 KiB
#include "swap.h" #include<bits/stdc++.h> using namespace std; int n; // weight then node vector<vector<pair<int, int>>> adj; void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n=N; adj = vector<vector<pair<int, int>>>(N); for(int i=0; i<M; i++) { adj[U[i]].push_back({W[i], V[i]}); adj[V[i]].push_back({W[i], U[i]}); } for(int i=0; i<N; i++) sort(adj[i].begin(), adj[i].end()); } int ans=0; set<pair<int, int>> noUse; vector<int> dijkstra(int s, int e) { vector<int> par(n), dis(n, 1e9); dis[s]=0; vector<bool> vis(n, false); priority_queue<pair<int, int>> q; q.push({0, s}); while(!q.empty()) { int node = q.top().second; q.pop(); if(vis[node]) continue; vis[node]=true; if(node == e) { ans=dis[e]; break; } for(auto [w, child] : adj[node]) if(!noUse.count({node, child})) { if(dis[child] > max(dis[node], w)) { dis[child]=max(dis[node], w); par[child]=node; q.push({-dis[child], child}); } } } vector<int> path; path.push_back(e); for(int i=e; i!=s; i=par[i]) { path.push_back(par[i]); } reverse(path.begin(), path.end()); return path; } int getMinimumFuelCapacity(int X, int Y) { ans=0; vector<int> path=dijkstra(X, Y); // for(auto x : path) cout << x << ' '; // cout << endl; int newAns=1e9; for(int i=0; i<path.size(); i++) { if(path[i] == X || path[i] == Y) { if(adj[path[i]].size() > 2) { if(adj[path[i]][2].first < ans) newAns=min(newAns, adj[path[i]][1].first); else newAns=min(newAns, adj[path[i]][2].first); } } else { bool f=false; for(int j=0; j<adj[path[i]].size(); j++) { if(!f && adj[path[i]][j].first == ans) f=true; else { newAns=min(newAns, adj[path[i]][j].first); break; } } } } //noUse.clear(); for(int i=1; i<path.size(); i++) { noUse.insert({path[i], path[i-1]}); noUse.insert({path[i-1], path[i]}); } int oldAns=ans; ans=0; dijkstra(X, Y); noUse.clear(); newAns=min(newAns, ans); return max(newAns, oldAns); }
#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...