oj.uz

Submission #678168

# Submission time Handle Problem Language Result Execution time Memory
678168 2023-01-05T09:26:51 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 343 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];
int par[maxn];

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]});
	}
	for(int i = 1; i <= N; i++){
		if(SZ(adj[i])==2) continue;
		dfs(i,-1); 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(SZ(adj[x])==1 and SZ(adj[y])==1) return -1;
	return -1;
	ll sum = dis[y]-dis[x], edgex = LINF, edgey=LINF;
	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 2664 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 11632 KB Output is correct
10 Correct 54 ms 13740 KB Output is correct
11 Correct 53 ms 13436 KB Output is correct
12 Correct 56 ms 14156 KB Output is correct
13 Correct 59 ms 14172 KB Output is correct
14 Correct 49 ms 12000 KB Output is correct
15 Correct 115 ms 17864 KB Output is correct
16 Correct 106 ms 17624 KB Output is correct
17 Correct 110 ms 18212 KB Output is correct
18 Correct 106 ms 18256 KB Output is correct
19 Incorrect 56 ms 7852 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 84 ms 11300 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 2664 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 343 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 343 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 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 2664 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 11632 KB Output is correct
10 Correct 54 ms 13740 KB Output is correct
11 Correct 53 ms 13436 KB Output is correct
12 Correct 56 ms 14156 KB Output is correct
13 Correct 59 ms 14172 KB Output is correct
14 Correct 49 ms 12000 KB Output is correct
15 Correct 115 ms 17864 KB Output is correct
16 Correct 106 ms 17624 KB Output is correct
17 Correct 110 ms 18212 KB Output is correct
18 Correct 106 ms 18256 KB Output is correct
19 Incorrect 84 ms 11300 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 343 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -