oj.uz

답안 #878242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878242 2023-11-24T07:40:05 Z boris_mihov 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 15204 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;

    for (const auto &[u, d] : g[node])
    {
        if (d > dist) continue;
        if (u == par)
        {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2796 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2856 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 113 ms 12772 KB Output is correct
10 Correct 328 ms 14356 KB Output is correct
11 Correct 346 ms 14520 KB Output is correct
12 Correct 436 ms 14668 KB Output is correct
13 Correct 574 ms 15204 KB Output is correct
14 Execution timed out 2051 ms 13020 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Execution timed out 2027 ms 14024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2796 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2856 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Incorrect 3 ms 2652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 2796 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2896 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2856 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 113 ms 12772 KB Output is correct
11 Correct 328 ms 14356 KB Output is correct
12 Correct 346 ms 14520 KB Output is correct
13 Correct 436 ms 14668 KB Output is correct
14 Correct 574 ms 15204 KB Output is correct
15 Incorrect 3 ms 2652 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2796 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2856 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 113 ms 12772 KB Output is correct
10 Correct 328 ms 14356 KB Output is correct
11 Correct 346 ms 14520 KB Output is correct
12 Correct 436 ms 14668 KB Output is correct
13 Correct 574 ms 15204 KB Output is correct
14 Execution timed out 2051 ms 13020 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 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 2796 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2896 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2856 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 113 ms 12772 KB Output is correct
11 Correct 328 ms 14356 KB Output is correct
12 Correct 346 ms 14520 KB Output is correct
13 Correct 436 ms 14668 KB Output is correct
14 Correct 574 ms 15204 KB Output is correct
15 Execution timed out 2051 ms 13020 KB Time limit exceeded
16 Halted 0 ms 0 KB -