oj.uz

Submission #405895

# Submission time Handle Problem Language Result Execution time Memory
405895 2021-05-17T03:12:58 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
0 / 100
 206 ms 27420 KB 
#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long

const int NN = 1e5+5;
int sub, used[NN], found, pos[NN], is[NN];
vector<int> pref[NN];
vector<pair<int, int>> edges[NN];
vector<pair<int, int>> ss;

void dfs(int u, int p = -1){
	if(used[u]){ found = 1; return; } 
	used[u] = 1;
	//cout<<u<<" ";
	for(auto x : edges[u]) { 
		if(x.ff == p) continue;
		ss.pb({u, x.ss});
		dfs(x.ff, u);
	}
}

void init(int32_t N, int32_t M,
	vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	//cout<<"\n";
	for(int i=0;i<M;i++){
		edges[U[i]].pb({V[i], W[i]});
		edges[V[i]].pb({U[i], W[i]});
	}
	int last = 0;
	for(int i=0;i<N;i++){
		if(used[i]) continue;
		ss.clear(), found = 0;
		dfs(i);
		if(found){
			pref[last].pb(0);
			ss.pop_back();
			for(int j=0;j<sz(ss);j++){
				is[ss[j].ff] = last+1;
				pos[ss[j].ff] = j+1;
				pref[last].pb(ss[j].ss);
			} for(int j=1;j<=sz(ss);j++) pref[last][j] += pref[last][j-1];
			last++;
		}
	} 
}

/*

5 5
1 0 1
2 1 2
3 2 3
4 3 4
4 0 5
5
0 1
1 2
2 3
3 4
4 0

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	if(x > y) swap(x, y);
	if(is[x] != is[y] || !is[x]) return -1;
	int l = is[x] - 1;
	int i = pos[x], j = pos[y];
	if(i > j) swap(i, j);
	return max(pref[l][j-1] - pref[l][i-1], pref[l][i-1] + pref[l][sz(pref[l])-1] - pref[l][j-1]);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5136 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 76 ms 19020 KB Output is correct
10 Correct 118 ms 23012 KB Output is correct
11 Correct 104 ms 21964 KB Output is correct
12 Correct 105 ms 23328 KB Output is correct
13 Correct 133 ms 25748 KB Output is correct
14 Correct 80 ms 18068 KB Output is correct
15 Correct 167 ms 24296 KB Output is correct
16 Correct 185 ms 22108 KB Output is correct
17 Correct 206 ms 27420 KB Output is correct
18 Correct 186 ms 25468 KB Output is correct
19 Incorrect 98 ms 12356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5136 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Incorrect 4 ms 4980 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4980 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5136 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 76 ms 19020 KB Output is correct
10 Correct 118 ms 23012 KB Output is correct
11 Correct 104 ms 21964 KB Output is correct
12 Correct 105 ms 23328 KB Output is correct
13 Correct 133 ms 25748 KB Output is correct
14 Correct 80 ms 18068 KB Output is correct
15 Correct 167 ms 24296 KB Output is correct
16 Correct 185 ms 22108 KB Output is correct
17 Correct 206 ms 27420 KB Output is correct
18 Correct 186 ms 25468 KB Output is correct
19 Incorrect 137 ms 16928 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4980 KB Output isn't correct