oj.uz

Submission #741164

# Submission time Handle Problem Language Result Execution time Memory
741164 2023-05-13T17:31:00 Z penguin133 Swapping Cities (APIO20_swap) C++17
0 / 100
 126 ms 17888 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(int i=0;i<N;i++)par[i] = i;
	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) {
  return -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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2696 KB Output is correct
9 Correct 55 ms 11352 KB Output is correct
10 Correct 64 ms 13236 KB Output is correct
11 Correct 60 ms 13092 KB Output is correct
12 Correct 63 ms 13776 KB Output is correct
13 Correct 58 ms 14016 KB Output is correct
14 Correct 58 ms 11624 KB Output is correct
15 Correct 126 ms 17320 KB Output is correct
16 Correct 115 ms 17084 KB Output is correct
17 Correct 126 ms 17620 KB Output is correct
18 Correct 106 ms 17888 KB Output is correct
19 Incorrect 53 ms 8176 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 99 ms 17180 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2696 KB Output is correct
9 Incorrect 3 ms 2660 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2660 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 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2696 KB Output is correct
9 Correct 55 ms 11352 KB Output is correct
10 Correct 64 ms 13236 KB Output is correct
11 Correct 60 ms 13092 KB Output is correct
12 Correct 63 ms 13776 KB Output is correct
13 Correct 58 ms 14016 KB Output is correct
14 Correct 58 ms 11624 KB Output is correct
15 Correct 126 ms 17320 KB Output is correct
16 Correct 115 ms 17084 KB Output is correct
17 Correct 126 ms 17620 KB Output is correct
18 Correct 106 ms 17888 KB Output is correct
19 Incorrect 99 ms 17180 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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