oj.uz

Submission #406783

# Submission time Handle Problem Language Result Execution time Memory
406783 2021-05-18T04:59:14 Z Maqsut_03 Swapping Cities (APIO20_swap) C++14
13 / 100
 168 ms 15844 KB 
#include "swap.h"
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <typeinfo>

#include <vector>
#include <array>
#include <valarray>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
#define ll int
#define pl pair<ll, ll>
#define llv vector<ll>
#define pv vector<pl>
#define pb push_back
#define ppb(x, y) push_back({x, y})
#define ff first
#define ss second
#define sz size()
using namespace std;
const int NN = 2 * 1e5 + 3, MOD = 1e9 + 7;

pl u0[NN];
pv v[NN];
ll n, m, k, d, u[NN];
bool f, f1, f2, f3;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) 
{
	n = N;
	m = M;
	for (int i=0; i<m; i++)
	{
		v[V[i]].ppb(U[i], W[i]);
		v[U[i]].ppb(V[i], W[i]);
		k = max(k, W[i]);
		
		u0[i] = {W[i], V[i]};
	}
	sort(u0, u0 + m);
	for (int i=0; i<m; i++) u[u0[i].ss] = u0[i].ff;
	d = u0[2].ff;
	int p = 0, q = 0;
	for (int i=0; i<n; i++)
	{
		if (v[i].sz == 1) q++;
		if (v[i].sz == 2) p++;
	}
	if (q == 2 && q + p == n) f = 1;
	
	if (m == n - 1 && v[0].sz == m) f1 = 1;
	f2 = 1;
	for (int i=0; i<n; i++)
	{
		if(v[i].sz != 2)
		{
			f2 = 0;
			break;
		}
	}
	return ;
}


int solve(int x, int y)
{
	ll dis[NN], val[NN], mn = MOD, mx;
	queue<int> q;
	bool u[NN], u0[NN];
	
	memset(val, -1, sizeof(val));
	q.push(x);
	dis[x] = -1;
    val[x] = 0;
		
	while (q.sz > 0)
	{
		ll a = q.front();
		u0[a] = 1;
		q.pop();

		for (auto i:v[a])
			if (!u0[i.ff])
			{
				if (val[i.ff] == -1)
				{
					val[i.ff] = max(val[a], i.ss);
					dis[i.ff] = a;
					q.push(i.ff);
				}
				else 
					if (max(i.ss, val[a]) < val[i.ff])
					{
						val[i.ff] = max(i.ss, val[a]);
						dis[i.ff] = a;
					}
			}
	}
	mx = val[y];
	while (dis[y] != -1) u[y] = 1, y = dis[y], q.push(y);
	
	while (q.sz > 0)
	{
		int i = q.front();
		q.pop();
		for (auto j:v[i])
			if (!u[j.ff]) mn = min(mn, j.ss);
	}
	
	return max(mn, mx);
}


int getMinimumFuelCapacity(int X, int Y) 
{
	if (f) return -1;
	if (f2) return k;
	if (f1) return max({d, u[X], u[Y]});
	
	return solve(X, Y);
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:61:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |  if (m == n - 1 && v[0].sz == m) f1 = 1;
      |                    ~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 54 ms 10392 KB Output is correct
10 Correct 71 ms 11540 KB Output is correct
11 Correct 85 ms 11468 KB Output is correct
12 Correct 89 ms 11860 KB Output is correct
13 Correct 93 ms 11816 KB Output is correct
14 Correct 62 ms 10528 KB Output is correct
15 Correct 146 ms 13736 KB Output is correct
16 Correct 168 ms 13560 KB Output is correct
17 Correct 137 ms 13868 KB Output is correct
18 Correct 132 ms 13868 KB Output is correct
19 Correct 82 ms 9640 KB Output is correct
20 Correct 145 ms 14564 KB Output is correct
21 Correct 146 ms 14584 KB Output is correct
22 Correct 149 ms 14972 KB Output is correct
23 Correct 142 ms 14980 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 144 ms 15484 KB Output is correct
4 Correct 131 ms 15752 KB Output is correct
5 Correct 126 ms 15752 KB Output is correct
6 Correct 126 ms 15604 KB Output is correct
7 Correct 130 ms 15844 KB Output is correct
8 Correct 122 ms 15420 KB Output is correct
9 Correct 130 ms 15504 KB Output is correct
10 Correct 122 ms 15408 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Incorrect 5 ms 6860 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6860 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 54 ms 10392 KB Output is correct
10 Correct 71 ms 11540 KB Output is correct
11 Correct 85 ms 11468 KB Output is correct
12 Correct 89 ms 11860 KB Output is correct
13 Correct 93 ms 11816 KB Output is correct
14 Correct 62 ms 10528 KB Output is correct
15 Correct 146 ms 13736 KB Output is correct
16 Correct 168 ms 13560 KB Output is correct
17 Correct 137 ms 13868 KB Output is correct
18 Correct 132 ms 13868 KB Output is correct
19 Correct 144 ms 15484 KB Output is correct
20 Correct 131 ms 15752 KB Output is correct
21 Correct 126 ms 15752 KB Output is correct
22 Correct 126 ms 15604 KB Output is correct
23 Correct 130 ms 15844 KB Output is correct
24 Correct 122 ms 15420 KB Output is correct
25 Correct 130 ms 15504 KB Output is correct
26 Correct 122 ms 15408 KB Output is correct
27 Incorrect 5 ms 6920 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6860 KB Output isn't correct