oj.uz

Submission #878270

# Submission time Handle Problem Language Result Execution time Memory
878270 2023-11-24T07:51:46 Z boris_mihov Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 16680 KB 
#include "swap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
 
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;
 
int n, m;
bool vis[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
 
bool dfs(int node, int par, int dist)
{
    bool res = false;
    vis[node] = true;
    int cnt = 0;
 
    for (const auto &[u, d] : g[node])
    {
        if (d > dist) continue;
        if (u == par && cnt == 0)
        {
            cnt++;
            continue;
        }
 
        if (vis[u])
        {
            res = true;
            continue;
        }
 
        res |= dfs(u, node, dist);
    }
 
    return res;
}
 
bool check(int u, int v, int dist)
{
    std::fill(vis + 1, vis + 1 + n, false);
    bool cycle = dfs(u, 0, dist);
    return cycle && vis[v];
}
 
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) 
{
    n = N; m = M;
    for (int i = 0 ; i < M ; ++i)
    {
        U[i]++; V[i]++;
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
}
 
int getMinimumFuelCapacity(int x, int y) 
{
    x++; y++;
    int l = 0, r = INF + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(x, y, mid)) l = mid;
        else r = mid;
    }
 
    if (r > INF) return -1;
    return r;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 135 ms 13848 KB Output is correct
10 Correct 346 ms 15680 KB Output is correct
11 Correct 631 ms 15848 KB Output is correct
12 Correct 606 ms 15864 KB Output is correct
13 Correct 917 ms 16680 KB Output is correct
14 Execution timed out 2041 ms 14260 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Execution timed out 2045 ms 13852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2904 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 135 ms 13848 KB Output is correct
11 Correct 346 ms 15680 KB Output is correct
12 Correct 631 ms 15848 KB Output is correct
13 Correct 606 ms 15864 KB Output is correct
14 Correct 917 ms 16680 KB Output is correct
15 Incorrect 2 ms 2652 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 135 ms 13848 KB Output is correct
10 Correct 346 ms 15680 KB Output is correct
11 Correct 631 ms 15848 KB Output is correct
12 Correct 606 ms 15864 KB Output is correct
13 Correct 917 ms 16680 KB Output is correct
14 Execution timed out 2041 ms 14260 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2904 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 135 ms 13848 KB Output is correct
11 Correct 346 ms 15680 KB Output is correct
12 Correct 631 ms 15848 KB Output is correct
13 Correct 606 ms 15864 KB Output is correct
14 Correct 917 ms 16680 KB Output is correct
15 Execution timed out 2041 ms 14260 KB Time limit exceeded
16 Halted 0 ms 0 KB -