Submission #985706

#TimeUsernameProblemLanguageResultExecution timeMemory
985706yoav_sSwapping Cities (APIO20_swap)C++17
37 / 100
2050 ms25244 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll,ll> p; typedef pair<ll, p> tri; typedef vector<ll> v; typedef vector<v> vv; typedef vector<p> vp; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<vv> vvv; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef vector<vvvp> vvvvp; #define double long double typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<vvd> vvvd; const ll mod = 1e9 + 7; const ll INF = 1e18; #define f first #define s second #define pb push_back #define eb emplace_back #define loop(a) for (ll i = 0; i < a; i++) #define setmin(a, b) a = min(a, b) #define setmax(a, b) a = max(a, b) #define all(v) v.begin(), v.end() #include "swap.h" ll res = -1; vvp graph; ll maxW = -INF; ll N; v weightInflate; void init(int Nn, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { N = Nn; for (auto x : W) weightInflate.pb(x); sort(all(weightInflate)); weightInflate.erase(unique(all(weightInflate)), weightInflate.end()); map<ll, ll> weightShrink; for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i; maxW = weightInflate.size() - 1; graph = vvp(N); for (ll i = 0; i < M; i++) { graph[U[i]].eb(V[i], weightShrink[W[i]]); graph[V[i]].eb(U[i], weightShrink[W[i]]); } } int getMinimumFuelCapacity(int X, int Y) { ll mini = 0, maxi = maxW + 1; while (mini < maxi) { ll mid = (mini + maxi) / 2; vv curGraph(N); for (ll i= 0 ; i < N; i++) { for (auto x : graph[i]) if (x.s <= mid) curGraph[i].pb(x.f); } v accessibleVertices; stack<ll> dfs; vb visited(N, false); dfs.push(X); while (!dfs.empty()) { auto top = dfs.top(); dfs.pop(); if (visited[top]) continue; visited[top] = true; accessibleVertices.pb(top); for (ll x : curGraph[top]) dfs.push(x); } bool poss = false; if (visited[Y]) { for (ll x : accessibleVertices) if (curGraph[x].size() >= 3) poss = true; ll edgeCount = 0; for (ll x : accessibleVertices) edgeCount += curGraph[x].size(); edgeCount /= 2; if (edgeCount >= accessibleVertices.size()) poss = true; } if (poss) { maxi = mid; } else { mini = mid + 1; } } if (mini > maxW) return -1; return weightInflate[mini]; } /* int main() { 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; } /**/

Compilation message (stderr)

swap.cpp:137:1: warning: "/*" within comment [-Wcomment]
  137 | /**/
      |  
swap.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:51:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i;
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:91:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       if (edgeCount >= accessibleVertices.size()) poss = true;
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...