oj.uz

Submission #1041888

# Submission time Handle Problem Language Result Execution time Memory
1041888 2024-08-02T09:16:06 Z Halym2007 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 17376 KB 
#include<bits/stdc++.h>
//#include "swap.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define pii pair <int, int>
const int N = 2e5 + 5;
vector <int> V, U, W, belle, belle1, yol;
int n, m, mx, mx1;

int a1, a2;
vector <pii> v[N];
int vis[N], vis1[N], vis2[N];
bool tt = 0;

void dfs (int x) {
	if (tt) return;
	vis[x] = 1;
	yol.pb (x);
	if (x == a2 and belle.empty()) {
		belle = yol;
		return;
	}
	for (pii i : v[x]) {
		if (vis[x]) continue;
		if (tt) return;
		mx = max (i.ss, mx);
		dfs (i.ff);
		if (tt) return;
	}
	yol.pop_back();
} 



void dfs1 (int x) {
	if (tt) return;
	vis1[x] = 1;
	yol.pb (x);
	if (x == a2 and belle1.empty()) {
		belle1 = yol;
		return;
	}
	for (pii i : v[x]) {
		if (vis1[x]) continue;
		if (tt) return;
		mx1 = max (i.ss, mx1);
		dfs1 (i.ff);
		if (tt) return;
	}
	yol.pop_back();
} 


void init(int N, int M, vector<int> U1, vector<int> V1, vector<int> W1) {
	n = N;m = M;V = V1;U = U1, W = W1;
	for (int i = 0; i < m; ++i) {
		v[U[i]].pb ({V[i], W[i]});
		v[V[i]].pb ({U[i], W[i]});
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int jogap = 2e9;
 	a1 = X;a2 = Y;
 	if (m <= 2) return -1;
	tt = 0;
	belle.clear();
	mx = 0, mx1 = 0;
	belle1.clear();
 	dfs (X);
	for (int i = 0; i < n; ++i) {
		vis[i] = 0;
	}
	for (int i = 0; i < (int)belle.sz; ++i) {
		vis[belle[i]] = 1;
	}
	tt = 0;
	dfs1(X);
	if (mx != 0 and mx1 != 0) jogap = max (mx, mx1);
	for (int i = 0; i < n; ++i) {
		vis1[i] = 0;
	}
	for (int i = 0; i < (int)belle1.sz; ++i) {
		vis1[belle1[i]] = 1;
	}
	int kl = 1e9, kl1 = 1e9;
	for (int i : belle) {
		for (pii j : v[i]) {
			if (vis[j.ff]) continue;
			kl = min (kl, j.ss);
		}
	}
	jogap = min (jogap, kl + mx);
	for (int i : belle1) {
		for (pii j : v[i]) {
			if (vis1[j.ff]) continue;
			kl1 = min (kl1, j.ss);
		}
	}
	jogap = min (jogap, kl1 + mx1);
	
	
	for (int i = 0; i < n; ++i) {
		vis1[i] = vis[i] = 0;;
	}
	
	if (jogap == 1e9) jogap = -1;
	return jogap;
	
}



//#include <cassert>
//#include <cstdio>
//
//#include <string>
//#include <vector>
//
//int main() {
//	freopen ("input.txt", "r", stdin);
//  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;
//}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7348 KB Output is correct
9 Correct 22 ms 11456 KB Output is correct
10 Correct 26 ms 12384 KB Output is correct
11 Correct 28 ms 12288 KB Output is correct
12 Correct 29 ms 12732 KB Output is correct
13 Correct 24 ms 12740 KB Output is correct
14 Correct 311 ms 11828 KB Output is correct
15 Execution timed out 2016 ms 17376 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Execution timed out 2070 ms 15360 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7348 KB Output is correct
9 Incorrect 1 ms 7416 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 7416 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 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7348 KB Output is correct
9 Correct 22 ms 11456 KB Output is correct
10 Correct 26 ms 12384 KB Output is correct
11 Correct 28 ms 12288 KB Output is correct
12 Correct 29 ms 12732 KB Output is correct
13 Correct 24 ms 12740 KB Output is correct
14 Correct 311 ms 11828 KB Output is correct
15 Execution timed out 2016 ms 17376 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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