Submission #985719

#TimeUsernameProblemLanguageResultExecution timeMemory
985719yoav_sSwapping Cities (APIO20_swap)C++17
17 / 100
2045 ms22732 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; ll getParent(ll i, v &dsuPar, v &times, ll time) { if (times[i] > time) return i; return getParent(dsuPar[i], dsuPar, times, time); } v dsuParent, timeBecomeNotRoot, dsuSize, timeValid; 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]]); } dsuParent = v(N); timeBecomeNotRoot = v(N, INF); dsuSize = v(N, 1); timeValid = v(N, INF); for (ll i = 0; i < N; i++) dsuParent[i] = i; vtri edgesByW; for (ll i = 0; i < M; i++) edgesByW.eb(weightShrink[W[i]], p(U[i], V[i])); sort(all(edgesByW)); v curDegree(N, 0); for (auto x : edgesByW) { ll l = x.s.f, r = x.s.s; ll p1 = getParent(l, dsuParent, timeBecomeNotRoot, x.f), p2 = getParent(r, dsuParent, timeBecomeNotRoot, x.f); if (p1 == p2) { timeValid[p1] = min(timeValid[p1], x.f); continue; } if (dsuSize[p1] < dsuSize[p2]) swap(p1, p2); dsuParent[p1] = p2; dsuSize[p2] += dsuSize[p1]; timeBecomeNotRoot[p1] = x.f; curDegree[l]++; curDegree[r]++; if ((timeValid[p1] < INF || curDegree[l] >= 3 || curDegree[r] >= 3) && timeValid[p2] == INF) timeValid[p2] = x.f; } } int getMinimumFuelCapacity(int X, int Y) { ll mini = 0, maxi = maxW + 1; while (mini < maxi) { ll mid = (mini + maxi) / 2; ll p1 = getParent(X, dsuParent, timeBecomeNotRoot, mid), p2 = getParent(Y, dsuParent, timeBecomeNotRoot, mid); bool poss = (p1 == p2 && timeValid[p1] <= mid); 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:142:1: warning: "/*" within comment [-Wcomment]
  142 | /**/
      |  
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:57:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
#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...