oj.uz

Submission #740800

# Submission time Handle Problem Language Result Execution time Memory
740800 2023-05-13T06:18:09 Z penguin133 Swapping Cities (APIO20_swap) C++17
0 / 100
 101 ms 10216 KB 
#include <bits/stdc++.h>
using namespace std;

//#include "swap.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <pi> adj[100005];
int par[100005];
pi mn[100005];
pi mn2[100005];
int mn3[100005];
int getr(int x){return (par[x] == x ? x : par[x] =getr(par[x]));}
void merge(int a, int b){a = getr(a); b = getr(b); if(a != b)par[b] = a;}

void init(int N, int M,
     std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	vector <pii> bru;
	for(int i=0;i<M;i++)bru.push_back({W[i], {U[i], V[i]}});
	for(int i=0;i<N;i++)mn[i] = mn2[i] = {2e9, 0}, mn3[i] = 2e9;
	sort(bru.begin(), bru.end());
	for(auto i : bru){
		int a = i.se.fi, b = i.se.se, w = i.fi;
		if(mn[a].fi == 2e9)mn[a] = {w, b};
		else if(mn2[a].fi == 2e9)mn2[a] = {w, b};
		else if(mn3[a] == 2e9)mn3[a] = w;
		if(mn[b].fi == 2e9)mn[b] = {w, a};
		else if(mn2[b].fi == 2e9)mn2[b] = {w, a};
		else if(mn3[b] == 2e9)mn3[b] = w;
		if(getr(a) == getr(b))continue;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
		merge(a, b);
	}
}

vector <int> path;
int tmp;
int tgt;
bool tr(int x, int par){
	if(x == tgt){
		path.push_back(x);
		return 1;
	}
	bool res = 0;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		bool tt = tr(i, x);
		res |= tt;
		if(tt)tmp = max(tmp, j);
	}
	if(res)path.push_back(x);
	return res;
}

int getMinimumFuelCapacity(int X, int Y) {
  tgt = Y;
  path.clear();
  tmp = 0;
  int bruh = tr(X, -1);
  int ouch = 2e9;
  for(int i=0;i<(int)path.size();i++){
	  int halp = mn[path[i]].se;
	  if(!(i && halp == path[i-1]) || (i < (int)path.size() - 1 && path[i+1] == halp))ouch = min(ouch, mn[path[i]].fi);
	  halp = mn2[path[i]].se;
	  if(!(i && halp == path[i-1]) || (i < (int)path.size() - 1 && path[i+1] == halp))ouch = min(ouch, mn2[path[i]].fi);
	  ouch = min(ouch, mn3[path[i]]);
  }
  if(ouch == 2e9)return -1;
  return max(ouch, tmp);
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:67:7: warning: unused variable 'bruh' [-Wunused-variable]
   67 |   int bruh = tr(X, -1);
      |       ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 34 ms 7356 KB Output is correct
10 Correct 46 ms 8324 KB Output is correct
11 Correct 38 ms 8244 KB Output is correct
12 Correct 41 ms 8640 KB Output is correct
13 Correct 41 ms 8648 KB Output is correct
14 Correct 38 ms 7488 KB Output is correct
15 Correct 101 ms 9952 KB Output is correct
16 Correct 92 ms 9776 KB Output is correct
17 Correct 90 ms 10216 KB Output is correct
18 Correct 93 ms 10176 KB Output is correct
19 Incorrect 50 ms 5828 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 87 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 1 ms 2644 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 34 ms 7356 KB Output is correct
10 Correct 46 ms 8324 KB Output is correct
11 Correct 38 ms 8244 KB Output is correct
12 Correct 41 ms 8640 KB Output is correct
13 Correct 41 ms 8648 KB Output is correct
14 Correct 38 ms 7488 KB Output is correct
15 Correct 101 ms 9952 KB Output is correct
16 Correct 92 ms 9776 KB Output is correct
17 Correct 90 ms 10216 KB Output is correct
18 Correct 93 ms 10176 KB Output is correct
19 Incorrect 87 ms 9728 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -