oj.uz

Submission #678172

# Submission time Handle Problem Language Result Execution time Memory
678172 2023-01-05T09:32:47 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 92 ms 10272 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 vis[maxn];

bool noCycle = false;
void dfs(int s, int p, int d=0){
	dis[s]=d; par[s]=p;vis[s]=1;
	for(auto u : adj[s]){
		if(!vis[u.fi]) 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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 37 ms 6880 KB Output is correct
10 Correct 42 ms 7908 KB Output is correct
11 Correct 43 ms 7744 KB Output is correct
12 Correct 44 ms 8064 KB Output is correct
13 Correct 44 ms 8052 KB Output is correct
14 Correct 38 ms 7028 KB Output is correct
15 Correct 91 ms 9716 KB Output is correct
16 Correct 91 ms 9576 KB Output is correct
17 Correct 92 ms 9880 KB Output is correct
18 Correct 91 ms 9864 KB Output is correct
19 Incorrect 44 ms 5924 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 1 ms 2644 KB Output is correct
3 Incorrect 80 ms 10272 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 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 37 ms 6880 KB Output is correct
10 Correct 42 ms 7908 KB Output is correct
11 Correct 43 ms 7744 KB Output is correct
12 Correct 44 ms 8064 KB Output is correct
13 Correct 44 ms 8052 KB Output is correct
14 Correct 38 ms 7028 KB Output is correct
15 Correct 91 ms 9716 KB Output is correct
16 Correct 91 ms 9576 KB Output is correct
17 Correct 92 ms 9880 KB Output is correct
18 Correct 91 ms 9864 KB Output is correct
19 Incorrect 80 ms 10272 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 -