Submission #1233467

#TimeUsernameProblemLanguageResultExecution timeMemory
1233467dssfsuper2Swapping Cities (APIO20_swap)C++20
0 / 100
2092 ms19180 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; vector<vector<pii>> adj; multiset<pii> stac; vector<pii> lowest; int n,m; int total=0; void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) { n=N; m=M; adj.resize(N+1); vector<int> deg(N+1); for(int i = 0;i<M;i++){ deg[U[i]]++; deg[V[i]]++; adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } if(*max_element(deg.begin(), deg.end())>=3)total=1; if(*min_element(deg.begin(), deg.end())==2 && *(max_element(deg.begin(), deg.end()))==2)total=1; } int dijkstra(int X, int Y){ stac.clear(); stac.insert({0, X}); lowest.assign(n+1, {1e9+1, 1e9+1}); lowest[X]={0, 1e9+1}; while(!stac.empty()){ auto node = *(stac.begin()); stac.erase(stac.begin()); if(lowest[node.second].second!=1e9+1 )continue; if(node.first>=lowest[node.second].first)lowest[node.second].second=node.first; else lowest[node.second].first=node.first; for(auto thing:adj[node.second]){ if(lowest[thing.first].second<=max(thing.second, node.first))continue; stac.insert({max(node.first, thing.second), thing.first}); } } return lowest[Y].second; } int getMinimumFuelCapacity(int X, int Y) { if(!total)return -1; return dijkstra(X, Y); }
#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...