Submission #974674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
974674	2024-05-03T15:37:44 Z	XXBabaProBerkay	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	15032 KB

swap

#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

using ll = long long;

bool ans;
vector<bool> vis;
vector<vector<pair<int, int>>> adj;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) //init(N, M, U, V, W)
{
	adj.resize(N);
	vis.resize(N);
	for (int i = 0; i < M; i++)
	{
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}
}

void DFS(int k, int p, int& t, int& x)
{
	if (vis[k])
	{
		ans = 1;
		return;
	}

	vis[k] = 1;
	for (auto i : adj[k])
		if (i.S <= x && i.F != p)
			DFS(i.F, k, t, x);
}

int getMinimumFuelCapacity(int X, int Y)
{
	int l = 1, r = 1e9;
	while (l <= r)
	{
		int m = (l + r) >> 1;
		ans = 0;
		fill(vis.begin(), vis.end(), 0);

		DFS(X, X, Y, m);

		if (ans && vis[Y])
			r = m - 1;
		else
			l = m + 1;
	}

	return (l < 1e9 ? l : -1);
}

Subtask #1

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	1 ms	348 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	2 ms	448 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	126 ms	12196 KB	Output is correct
10	Correct	253 ms	14000 KB	Output is correct
11	Correct	365 ms	14068 KB	Output is correct
12	Correct	345 ms	14504 KB	Output is correct
13	Correct	529 ms	15032 KB	Output is correct
14	Execution timed out	2036 ms	12736 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

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	Execution timed out	2004 ms	13732 KB	Time limit exceeded
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	1 ms	348 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	2 ms	448 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Incorrect	2 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 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	2 ms	348 KB	Output is correct
7	Correct	2 ms	448 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	126 ms	12196 KB	Output is correct
11	Correct	253 ms	14000 KB	Output is correct
12	Correct	365 ms	14068 KB	Output is correct
13	Correct	345 ms	14504 KB	Output is correct
14	Correct	529 ms	15032 KB	Output is correct
15	Incorrect	2 ms	348 KB	Output isn't correct
16	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	1 ms	348 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	2 ms	448 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	126 ms	12196 KB	Output is correct
10	Correct	253 ms	14000 KB	Output is correct
11	Correct	365 ms	14068 KB	Output is correct
12	Correct	345 ms	14504 KB	Output is correct
13	Correct	529 ms	15032 KB	Output is correct
14	Execution timed out	2036 ms	12736 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 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	2 ms	348 KB	Output is correct
7	Correct	2 ms	448 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	126 ms	12196 KB	Output is correct
11	Correct	253 ms	14000 KB	Output is correct
12	Correct	365 ms	14068 KB	Output is correct
13	Correct	345 ms	14504 KB	Output is correct
14	Correct	529 ms	15032 KB	Output is correct
15	Execution timed out	2036 ms	12736 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-