oj.uz

Submission #678169

# Submission time Handle Problem Language Result Execution time Memory
678169 2023-01-05T09:30:22 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 327 ms 524288 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;
		dfs(i,-1); noCycle=true; break;
	}
}
/*
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 2 ms 2772 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 2684 KB Output is correct
6 Correct 3 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 47 ms 10728 KB Output is correct
10 Correct 66 ms 12360 KB Output is correct
11 Correct 57 ms 12232 KB Output is correct
12 Correct 57 ms 12748 KB Output is correct
13 Correct 66 ms 12780 KB Output is correct
14 Correct 50 ms 10828 KB Output is correct
15 Correct 120 ms 14304 KB Output is correct
16 Correct 106 ms 14040 KB Output is correct
17 Correct 117 ms 14592 KB Output is correct
18 Correct 121 ms 14580 KB Output is correct
19 Incorrect 49 ms 6532 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 2 ms 2772 KB Output is correct
3 Incorrect 84 ms 11428 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 2 ms 2772 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 2684 KB Output is correct
6 Correct 3 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 Runtime error 327 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 524288 KB Execution killed with signal 9
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 2 ms 2772 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 2684 KB Output is correct
6 Correct 3 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 47 ms 10728 KB Output is correct
10 Correct 66 ms 12360 KB Output is correct
11 Correct 57 ms 12232 KB Output is correct
12 Correct 57 ms 12748 KB Output is correct
13 Correct 66 ms 12780 KB Output is correct
14 Correct 50 ms 10828 KB Output is correct
15 Correct 120 ms 14304 KB Output is correct
16 Correct 106 ms 14040 KB Output is correct
17 Correct 117 ms 14592 KB Output is correct
18 Correct 121 ms 14580 KB Output is correct
19 Incorrect 84 ms 11428 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -