# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1000788 |
2024-06-18T08:48:56 Z |
uranhishig |
Race (IOI11_race) |
C++14 |
|
3000 ms |
29520 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mid(l,r) ((r+l)/2)
#define left(node) (node*2)
#define right(node) (node*2+1)
#define mx_int_prime 999999937
#define mod 1000000007
#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define sqr(a) ((a) * (a))
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fastio cin.tie(0)->sync_with_stdio(0)
#define print(x) cout << x << "\n"
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const int MAXN = 1e6;
vector<pair<int, int>> adj[MAXN];
bool visited[MAXN];
int mi = INT_MAX;
void dfs(int node, int x, int y, int z) {
visited[node] = true;
if (x == y) {
mi = min(mi, z);
}
else {
for (auto neighbor : adj[node]) {
int nextCity = neighbor.f;
int length = neighbor.s;
if (!visited[nextCity] && x + length <= y) {
dfs(nextCity, x + length, y, z + 1);
}
}
}
visited[node] = false;
}
int best_path(int N, int K, int H[][2], int L[]) {
rep(i, N-1) {
int city1 = H[i][0], city2 = H[i][1], length = L[i];
adj[city1].emplace_back(city2, length);
adj[city2].emplace_back(city1, length);
}
mi = INT_MAX;
for (int st = 0; st < N; st++) {
memset(visited, false, sizeof(visited));
dfs(st, 0, K, 0);
}
if (mi == INT_MAX) {
return -1;
} else {
return mi;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
24668 KB |
Output is correct |
2 |
Correct |
11 ms |
24768 KB |
Output is correct |
3 |
Correct |
10 ms |
24668 KB |
Output is correct |
4 |
Correct |
11 ms |
24924 KB |
Output is correct |
5 |
Correct |
11 ms |
24704 KB |
Output is correct |
6 |
Correct |
11 ms |
24664 KB |
Output is correct |
7 |
Correct |
11 ms |
24668 KB |
Output is correct |
8 |
Correct |
10 ms |
24920 KB |
Output is correct |
9 |
Correct |
12 ms |
24668 KB |
Output is correct |
10 |
Correct |
10 ms |
24668 KB |
Output is correct |
11 |
Correct |
12 ms |
24716 KB |
Output is correct |
12 |
Correct |
10 ms |
24924 KB |
Output is correct |
13 |
Correct |
11 ms |
24924 KB |
Output is correct |
14 |
Correct |
11 ms |
24668 KB |
Output is correct |
15 |
Correct |
11 ms |
24924 KB |
Output is correct |
16 |
Correct |
11 ms |
24664 KB |
Output is correct |
17 |
Correct |
10 ms |
24924 KB |
Output is correct |
18 |
Correct |
11 ms |
24920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
24668 KB |
Output is correct |
2 |
Correct |
11 ms |
24768 KB |
Output is correct |
3 |
Correct |
10 ms |
24668 KB |
Output is correct |
4 |
Correct |
11 ms |
24924 KB |
Output is correct |
5 |
Correct |
11 ms |
24704 KB |
Output is correct |
6 |
Correct |
11 ms |
24664 KB |
Output is correct |
7 |
Correct |
11 ms |
24668 KB |
Output is correct |
8 |
Correct |
10 ms |
24920 KB |
Output is correct |
9 |
Correct |
12 ms |
24668 KB |
Output is correct |
10 |
Correct |
10 ms |
24668 KB |
Output is correct |
11 |
Correct |
12 ms |
24716 KB |
Output is correct |
12 |
Correct |
10 ms |
24924 KB |
Output is correct |
13 |
Correct |
11 ms |
24924 KB |
Output is correct |
14 |
Correct |
11 ms |
24668 KB |
Output is correct |
15 |
Correct |
11 ms |
24924 KB |
Output is correct |
16 |
Correct |
11 ms |
24664 KB |
Output is correct |
17 |
Correct |
10 ms |
24924 KB |
Output is correct |
18 |
Correct |
11 ms |
24920 KB |
Output is correct |
19 |
Correct |
8 ms |
24668 KB |
Output is correct |
20 |
Correct |
10 ms |
24916 KB |
Output is correct |
21 |
Correct |
38 ms |
24720 KB |
Output is correct |
22 |
Correct |
28 ms |
24924 KB |
Output is correct |
23 |
Correct |
28 ms |
24924 KB |
Output is correct |
24 |
Correct |
27 ms |
24920 KB |
Output is correct |
25 |
Correct |
39 ms |
24924 KB |
Output is correct |
26 |
Correct |
28 ms |
24920 KB |
Output is correct |
27 |
Correct |
31 ms |
24920 KB |
Output is correct |
28 |
Correct |
30 ms |
24920 KB |
Output is correct |
29 |
Correct |
33 ms |
24920 KB |
Output is correct |
30 |
Correct |
35 ms |
24924 KB |
Output is correct |
31 |
Correct |
41 ms |
24924 KB |
Output is correct |
32 |
Correct |
39 ms |
24940 KB |
Output is correct |
33 |
Correct |
38 ms |
24924 KB |
Output is correct |
34 |
Correct |
29 ms |
24924 KB |
Output is correct |
35 |
Correct |
28 ms |
24924 KB |
Output is correct |
36 |
Correct |
26 ms |
24944 KB |
Output is correct |
37 |
Correct |
31 ms |
24924 KB |
Output is correct |
38 |
Correct |
35 ms |
24924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
24668 KB |
Output is correct |
2 |
Correct |
11 ms |
24768 KB |
Output is correct |
3 |
Correct |
10 ms |
24668 KB |
Output is correct |
4 |
Correct |
11 ms |
24924 KB |
Output is correct |
5 |
Correct |
11 ms |
24704 KB |
Output is correct |
6 |
Correct |
11 ms |
24664 KB |
Output is correct |
7 |
Correct |
11 ms |
24668 KB |
Output is correct |
8 |
Correct |
10 ms |
24920 KB |
Output is correct |
9 |
Correct |
12 ms |
24668 KB |
Output is correct |
10 |
Correct |
10 ms |
24668 KB |
Output is correct |
11 |
Correct |
12 ms |
24716 KB |
Output is correct |
12 |
Correct |
10 ms |
24924 KB |
Output is correct |
13 |
Correct |
11 ms |
24924 KB |
Output is correct |
14 |
Correct |
11 ms |
24668 KB |
Output is correct |
15 |
Correct |
11 ms |
24924 KB |
Output is correct |
16 |
Correct |
11 ms |
24664 KB |
Output is correct |
17 |
Correct |
10 ms |
24924 KB |
Output is correct |
18 |
Correct |
11 ms |
24920 KB |
Output is correct |
19 |
Execution timed out |
3036 ms |
29520 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
24668 KB |
Output is correct |
2 |
Correct |
11 ms |
24768 KB |
Output is correct |
3 |
Correct |
10 ms |
24668 KB |
Output is correct |
4 |
Correct |
11 ms |
24924 KB |
Output is correct |
5 |
Correct |
11 ms |
24704 KB |
Output is correct |
6 |
Correct |
11 ms |
24664 KB |
Output is correct |
7 |
Correct |
11 ms |
24668 KB |
Output is correct |
8 |
Correct |
10 ms |
24920 KB |
Output is correct |
9 |
Correct |
12 ms |
24668 KB |
Output is correct |
10 |
Correct |
10 ms |
24668 KB |
Output is correct |
11 |
Correct |
12 ms |
24716 KB |
Output is correct |
12 |
Correct |
10 ms |
24924 KB |
Output is correct |
13 |
Correct |
11 ms |
24924 KB |
Output is correct |
14 |
Correct |
11 ms |
24668 KB |
Output is correct |
15 |
Correct |
11 ms |
24924 KB |
Output is correct |
16 |
Correct |
11 ms |
24664 KB |
Output is correct |
17 |
Correct |
10 ms |
24924 KB |
Output is correct |
18 |
Correct |
11 ms |
24920 KB |
Output is correct |
19 |
Correct |
8 ms |
24668 KB |
Output is correct |
20 |
Correct |
10 ms |
24916 KB |
Output is correct |
21 |
Correct |
38 ms |
24720 KB |
Output is correct |
22 |
Correct |
28 ms |
24924 KB |
Output is correct |
23 |
Correct |
28 ms |
24924 KB |
Output is correct |
24 |
Correct |
27 ms |
24920 KB |
Output is correct |
25 |
Correct |
39 ms |
24924 KB |
Output is correct |
26 |
Correct |
28 ms |
24920 KB |
Output is correct |
27 |
Correct |
31 ms |
24920 KB |
Output is correct |
28 |
Correct |
30 ms |
24920 KB |
Output is correct |
29 |
Correct |
33 ms |
24920 KB |
Output is correct |
30 |
Correct |
35 ms |
24924 KB |
Output is correct |
31 |
Correct |
41 ms |
24924 KB |
Output is correct |
32 |
Correct |
39 ms |
24940 KB |
Output is correct |
33 |
Correct |
38 ms |
24924 KB |
Output is correct |
34 |
Correct |
29 ms |
24924 KB |
Output is correct |
35 |
Correct |
28 ms |
24924 KB |
Output is correct |
36 |
Correct |
26 ms |
24944 KB |
Output is correct |
37 |
Correct |
31 ms |
24924 KB |
Output is correct |
38 |
Correct |
35 ms |
24924 KB |
Output is correct |
39 |
Execution timed out |
3036 ms |
29520 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |