oj.uz

답안 #740795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740795 2023-05-13T06:13:07 Z penguin133 자매 도시 (APIO20_swap) C++17
0 / 100
 113 ms 13848 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(getr(a) == getr(b))continue;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
		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;
		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:64:7: warning: unused variable 'bruh' [-Wunused-variable]
   64 |   int bruh = tr(X, -1);
      |       ^~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 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 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 45 ms 8388 KB Output is correct
10 Correct 46 ms 9644 KB Output is correct
11 Correct 43 ms 9484 KB Output is correct
12 Correct 57 ms 9960 KB Output is correct
13 Correct 59 ms 9980 KB Output is correct
14 Correct 43 ms 8736 KB Output is correct
15 Correct 108 ms 13628 KB Output is correct
16 Correct 106 ms 13352 KB Output is correct
17 Correct 110 ms 13772 KB Output is correct
18 Correct 113 ms 13848 KB Output is correct
19 Incorrect 55 ms 7696 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Incorrect 99 ms 12828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 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 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 2 ms 2644 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 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 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 45 ms 8388 KB Output is correct
10 Correct 46 ms 9644 KB Output is correct
11 Correct 43 ms 9484 KB Output is correct
12 Correct 57 ms 9960 KB Output is correct
13 Correct 59 ms 9980 KB Output is correct
14 Correct 43 ms 8736 KB Output is correct
15 Correct 108 ms 13628 KB Output is correct
16 Correct 106 ms 13352 KB Output is correct
17 Correct 110 ms 13772 KB Output is correct
18 Correct 113 ms 13848 KB Output is correct
19 Incorrect 99 ms 12828 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -