Submission #406805

#TimeUsernameProblemLanguageResultExecution timeMemory
406805Maqsut_03Swapping Cities (APIO20_swap)C++14
13 / 100
158 ms15288 KiB
#include "swap.h" #include <iomanip> #include <algorithm> #include <numeric> #include <functional> #include <typeinfo> #include <vector> #include <array> #include <valarray> #include <queue> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <cassert> #define ll int #define pl pair<ll, ll> #define llv vector<ll> #define pv vector<pl> #define pb push_back #define ppb(x, y) push_back({x, y}) #define ff first #define ss second #define sz size() using namespace std; const int NN = 2 * 1e5 + 3, MOD = 1e9 + 7; pl u0[NN]; pv v[NN]; ll n, m, k, d, u[NN]; bool f, f1, f2, f3; void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N; m = M; for (int i=0; i<m; i++) { v[V[i]].ppb(U[i], W[i]); v[U[i]].ppb(V[i], W[i]); k = max(k, W[i]); u0[i] = {W[i], V[i]}; } sort(u0, u0 + m); for (int i=0; i<m; i++) u[u0[i].ss] = u0[i].ff; d = u0[2].ff; int p = 0, q = 0; for (int i=0; i<n; i++) { if (v[i].sz == 1) q++; if (v[i].sz == 2) p++; } if (q == 2 && q + p == n) f = 1; if (m == n - 1 && v[0].sz == m) f1 = 1; f2 = 1; for (int i=0; i<n; i++) { if(v[i].sz != 2) { f2 = 0; break; } } return ; } int solve(int x, int y) { ll dis[NN], val[NN], mn = MOD, mx; queue<int> q; bool u[NN], u0[NN]; memset(val, -1, sizeof(val)); q.push(x); dis[x] = -1; val[x] = 0; while (q.sz > 0) { ll a = q.front(); u0[a] = 1; q.pop(); for (auto i:v[a]) if (!u0[i.ff]) { if (val[i.ff] == -1) { val[i.ff] = max(val[a], i.ss); dis[i.ff] = a; q.push(i.ff); } else if (max(i.ss, val[a]) < val[i.ff]) { val[i.ff] = max(i.ss, val[a]); dis[i.ff] = a; } } } mx = val[y]; while (dis[y] != -1) { u[y] = 1; y = dis[y]; if (dis[y] != -1) q.push(y); } u[x] = 1; while (q.sz > 0) { int i = q.front(); q.pop(); for (auto j:v[i]) if (!u[j.ff]) mn = min(mn, j.ss); } return max(mn, mx); } int getMinimumFuelCapacity(int X, int Y) { if (f) return -1; if (f2) return k; if (f1) return max({d, u[X], u[Y]}); return 1; return solve(X, Y); }

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:61:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |  if (m == n - 1 && v[0].sz == m) f1 = 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...