oj.uz

Submission #678170

# Submission time Handle Problem Language Result Execution time Memory
678170 2023-01-05T09:31:49 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 101 ms 10280 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define SZ(a) (int)a.size()
using ll = long long;

const int maxn = (int)1e5+10;
const ll LINF = (ll)1e18;

vector<pair<int,int>> adj[maxn];
ll dis[maxn], tot = 0;
int par[maxn];
bool noCycle = false;
void dfs(int s, int p, int d=0){
	dis[s]=d; par[s]=p;
	for(auto u : adj[s]){
		if(u.fi!=p) dfs(u.fi,s, d+u.se);
	}
}

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	for(int i = 0; i < M; i++){
		adj[u[i]].pb({v[i],w[i]});
		adj[v[i]].pb({u[i],w[i]}); tot+=w[i];
	}
	for(int i = 1; i <= N; i++){
		if(SZ(adj[i])==2) continue;
		 noCycle=true; break;
	}
	if(!noCycle) dfs(0,-1);
}
/*
5 4
1 2 3
2 3 4
3 4 5
4 5 6
4
1 2
1 5
2 5
2 4
*/

int getMinimumFuelCapacity(int x, int y) {
	if(dis[x]>dis[y]) swap(x,y);
	if(noCycle) return -1;
	ll sum = dis[y]-dis[x], edgex = LINF, edgey=LINF;
	return max(sum, tot-sum);
	if(SZ(adj[y])!=1)
		for(auto u : adj[y])
			if(dis[u.fi]>dis[y]) edgey=u.se;
	if(SZ(adj[x])!=1)
		for(auto u : adj[x])
			if(dis[u.fi]<dis[x]) edgex=u.se;
	return sum+min(edgex,edgey);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 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 2644 KB Output is correct
9 Correct 35 ms 6916 KB Output is correct
10 Correct 49 ms 7876 KB Output is correct
11 Correct 46 ms 7744 KB Output is correct
12 Correct 44 ms 8052 KB Output is correct
13 Correct 44 ms 8116 KB Output is correct
14 Correct 46 ms 6988 KB Output is correct
15 Correct 101 ms 9712 KB Output is correct
16 Correct 96 ms 9596 KB Output is correct
17 Correct 98 ms 9844 KB Output is correct
18 Correct 92 ms 9824 KB Output is correct
19 Incorrect 45 ms 5812 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 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 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 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

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 1 ms 2644 KB Output is correct
2 Correct 1 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 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 2644 KB Output is correct
9 Correct 35 ms 6916 KB Output is correct
10 Correct 49 ms 7876 KB Output is correct
11 Correct 46 ms 7744 KB Output is correct
12 Correct 44 ms 8052 KB Output is correct
13 Correct 44 ms 8116 KB Output is correct
14 Correct 46 ms 6988 KB Output is correct
15 Correct 101 ms 9712 KB Output is correct
16 Correct 96 ms 9596 KB Output is correct
17 Correct 98 ms 9844 KB Output is correct
18 Correct 92 ms 9824 KB Output is correct
19 Incorrect 86 ms 10280 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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