oj.uz

Submission #740797

# Submission time Handle Problem Language Result Execution time Memory
740797 2023-05-13T06:14:13 Z penguin133 Swapping Cities (APIO20_swap) C++17
0 / 100
 89 ms 9348 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];
int mn2[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] = {2e9, 0}, mn2[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] == 2e9)mn2[a] = w;
		if(mn[b].fi == 2e9)mn[b] = {w, a};
		else if(mn2[b] == 2e9)mn2[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, mn2[path[i]]);
	  else ouch = min(ouch, mn[path[i]].fi);
  }
  if(ouch == 2e9)return -1;
  return max(ouch, tmp);
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 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 2708 KB Output is correct
9 Correct 34 ms 6768 KB Output is correct
10 Correct 43 ms 7608 KB Output is correct
11 Correct 36 ms 7600 KB Output is correct
12 Correct 40 ms 7860 KB Output is correct
13 Correct 43 ms 7788 KB Output is correct
14 Correct 37 ms 6892 KB Output is correct
15 Correct 82 ms 9160 KB Output is correct
16 Correct 83 ms 9024 KB Output is correct
17 Correct 88 ms 9348 KB Output is correct
18 Correct 89 ms 9344 KB Output is correct
19 Incorrect 44 ms 5760 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 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 2708 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 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 2708 KB Output is correct
9 Correct 34 ms 6768 KB Output is correct
10 Correct 43 ms 7608 KB Output is correct
11 Correct 36 ms 7600 KB Output is correct
12 Correct 40 ms 7860 KB Output is correct
13 Correct 43 ms 7788 KB Output is correct
14 Correct 37 ms 6892 KB Output is correct
15 Correct 82 ms 9160 KB Output is correct
16 Correct 83 ms 9024 KB Output is correct
17 Correct 88 ms 9348 KB Output is correct
18 Correct 89 ms 9344 KB Output is correct
19 Incorrect 80 ms 9008 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 -