oj.uz

Submission #979807

# Submission time Handle Problem Language Result Execution time Memory
979807 2024-05-11T11:52:22 Z Marcus Swapping Cities (APIO20_swap) C++17
6 / 100
 89 ms 18940 KB 
#include <swap.h>
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> adj;

namespace subtask1 {
    bool cycle = false;
    int gas = 0;
	vector<bool> visited;
    void dfs(int s, int v)
    {
    	if (visited[s]) return;
    	visited[s] = true;
    	for (auto u: adj[s])
    	{
    		if (visited[u.first] && u.first != v) cycle = true;
    		gas = max(gas, u.second);
    		dfs(u.first, s);
    	}
    }
}

namespace subtask2 {
	bool nodes = false;
	bool variation = false;
	bool execution = false;
	vector<pair<int, int>> edge;
	int gas = 0;
}

void init(int n1, int m1, vector<int> v, vector<int> u, vector<int> w) {
	n = n1;
	m = m1;
	adj.resize(n);
	for (int i=0; i<m; i++)
	{
		adj[v[i]].push_back({u[i], w[i]});
		adj[u[i]].push_back({v[i], w[i]});
	}

	//subtask1
	subtask1::visited.resize(n);

	//subtask2
	if (m == (n-1)) {subtask2::nodes = true;}
	for (auto s: v) {if (s != 0) {subtask2::variation = true;}}
	subtask2::execution = (subtask2::nodes && !(subtask2::variation));

	if (subtask2::execution) 
	{
		for (auto u: adj[0]) 
		{
			subtask2::edge.push_back({u.second, u.first});
		}
		sort(subtask2::edge.begin(), subtask2::edge.end());
		subtask2::edge.erase(subtask2::edge.begin()+3, subtask2::edge.end());
	}
}

int getMinimumFuelCapacity(int x, int y){
	if (subtask2::execution) 
	{
		if (n < 4) return -1;
		subtask2::gas = max(adj[x][0].second, adj[y][0].second);
		for (auto &u: subtask2::edge)
		{
			if (u.second != x && u.second != y) {return max(u.first, subtask2::gas);}
		}
	}
	else 
	{
	    subtask1::dfs(1, 0);
	    return (subtask1::cycle ? subtask1::gas : -1);
	}
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
   76 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 31 ms 9932 KB Output is correct
10 Correct 37 ms 12008 KB Output is correct
11 Correct 39 ms 10884 KB Output is correct
12 Correct 38 ms 11788 KB Output is correct
13 Correct 50 ms 12856 KB Output is correct
14 Correct 34 ms 9396 KB Output is correct
15 Correct 79 ms 15840 KB Output is correct
16 Correct 76 ms 14592 KB Output is correct
17 Correct 89 ms 15868 KB Output is correct
18 Correct 83 ms 16704 KB Output is correct
19 Correct 42 ms 7252 KB Output is correct
20 Correct 78 ms 17872 KB Output is correct
21 Correct 81 ms 18032 KB Output is correct
22 Correct 84 ms 18940 KB Output is correct
23 Correct 82 ms 18808 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 31 ms 9932 KB Output is correct
10 Correct 37 ms 12008 KB Output is correct
11 Correct 39 ms 10884 KB Output is correct
12 Correct 38 ms 11788 KB Output is correct
13 Correct 50 ms 12856 KB Output is correct
14 Correct 34 ms 9396 KB Output is correct
15 Correct 79 ms 15840 KB Output is correct
16 Correct 76 ms 14592 KB Output is correct
17 Correct 89 ms 15868 KB Output is correct
18 Correct 83 ms 16704 KB Output is correct
19 Incorrect 78 ms 14664 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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