oj.uz

Submission #678181

# Submission time Handle Problem Language Result Execution time Memory
678181 2023-01-05T09:37:27 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 119 ms 10244 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 tot;
	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 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 50 ms 6912 KB Output is correct
10 Correct 53 ms 7900 KB Output is correct
11 Correct 46 ms 7744 KB Output is correct
12 Correct 72 ms 8020 KB Output is correct
13 Correct 48 ms 8012 KB Output is correct
14 Correct 39 ms 7028 KB Output is correct
15 Correct 102 ms 9720 KB Output is correct
16 Correct 106 ms 9588 KB Output is correct
17 Correct 106 ms 9832 KB Output is correct
18 Correct 119 ms 9812 KB Output is correct
19 Incorrect 47 ms 5876 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 89 ms 10244 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 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 1 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 1 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 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 50 ms 6912 KB Output is correct
10 Correct 53 ms 7900 KB Output is correct
11 Correct 46 ms 7744 KB Output is correct
12 Correct 72 ms 8020 KB Output is correct
13 Correct 48 ms 8012 KB Output is correct
14 Correct 39 ms 7028 KB Output is correct
15 Correct 102 ms 9720 KB Output is correct
16 Correct 106 ms 9588 KB Output is correct
17 Correct 106 ms 9832 KB Output is correct
18 Correct 119 ms 9812 KB Output is correct
19 Incorrect 89 ms 10244 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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