oj.uz

답안 #878291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878291 2023-11-24T08:02:00 Z boris_mihov 자매 도시 (APIO20_swap) C++17
37 / 100
 2000 ms 20768 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)
{
    int deg = 0;
    bool res = false;
    vis[node] = true;

    for (const auto &[u, d] : g[node])
    {
        if (d > dist) 
        {
            continue;
        }

        deg++;
        if (u == par)
        {
            continue;
        }

        if (vis[u])
        {
            res = true;
            continue;
        }
 
        res |= dfs(u, node, dist);
    }
    
    res |= (deg >= 3);
    return res;
}

void clearDFS(int node)
{
    vis[node] = false;
    for (const auto &[u, d] : g[node])
    {
        if (vis[u])
        {
            clearDFS(u);
        }
    }
}
 
bool check(int u, int v, int dist)
{
    bool res = dfs(u, 0, dist) && vis[v];
    clearDFS(u);
    return res;
}
 
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 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 2 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 3 ms 2920 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 198 ms 12524 KB Output is correct
10 Correct 545 ms 13548 KB Output is correct
11 Correct 669 ms 13852 KB Output is correct
12 Correct 661 ms 13756 KB Output is correct
13 Correct 947 ms 14684 KB Output is correct
14 Execution timed out 2016 ms 12472 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
17.0 / 17.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 2 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 3 ms 2920 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 3 ms 2896 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 3 ms 2868 KB Output is correct
17 Correct 3 ms 2908 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 4 ms 2912 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 2 ms 2844 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 3 ms 2904 KB Output is correct
25 Correct 3 ms 2916 KB Output is correct
26 Correct 6 ms 2908 KB Output is correct
27 Correct 3 ms 2908 KB Output is correct
28 Correct 4 ms 2908 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2648 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 3 ms 2652 KB Output is correct
7 Correct 3 ms 3160 KB Output is correct
8 Correct 3 ms 2920 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 198 ms 12524 KB Output is correct
11 Correct 545 ms 13548 KB Output is correct
12 Correct 669 ms 13852 KB Output is correct
13 Correct 661 ms 13756 KB Output is correct
14 Correct 947 ms 14684 KB Output is correct
15 Correct 2 ms 2648 KB Output is correct
16 Correct 3 ms 2896 KB Output is correct
17 Correct 3 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2648 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 3 ms 2868 KB Output is correct
22 Correct 3 ms 2908 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 4 ms 2912 KB Output is correct
26 Correct 3 ms 2652 KB Output is correct
27 Correct 2 ms 2844 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 3 ms 2904 KB Output is correct
30 Correct 3 ms 2916 KB Output is correct
31 Correct 6 ms 2908 KB Output is correct
32 Correct 3 ms 2908 KB Output is correct
33 Correct 4 ms 2908 KB Output is correct
34 Correct 17 ms 3676 KB Output is correct
35 Correct 815 ms 14776 KB Output is correct
36 Correct 823 ms 12316 KB Output is correct
37 Correct 759 ms 10180 KB Output is correct
38 Correct 943 ms 9812 KB Output is correct
39 Correct 750 ms 9808 KB Output is correct
40 Correct 784 ms 9564 KB Output is correct
41 Correct 646 ms 13236 KB Output is correct
42 Correct 1004 ms 14092 KB Output is correct
43 Correct 706 ms 16116 KB Output is correct
44 Correct 405 ms 10836 KB Output is correct
45 Correct 663 ms 15324 KB Output is correct
46 Correct 888 ms 14308 KB Output is correct
47 Correct 874 ms 9976 KB Output is correct
48 Correct 739 ms 10748 KB Output is correct
49 Correct 96 ms 14172 KB Output is correct
50 Correct 124 ms 11088 KB Output is correct
51 Correct 425 ms 13548 KB Output is correct
52 Correct 562 ms 17984 KB Output is correct
53 Correct 397 ms 16332 KB Output is correct
54 Correct 1477 ms 20768 KB Output is correct
55 Correct 823 ms 16088 KB Output is correct
56 Correct 863 ms 17520 KB Output is correct

Subtask #5
0 / 23.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 2 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 3 ms 2920 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 198 ms 12524 KB Output is correct
10 Correct 545 ms 13548 KB Output is correct
11 Correct 669 ms 13852 KB Output is correct
12 Correct 661 ms 13756 KB Output is correct
13 Correct 947 ms 14684 KB Output is correct
14 Execution timed out 2016 ms 12472 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2648 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 3 ms 2652 KB Output is correct
7 Correct 3 ms 3160 KB Output is correct
8 Correct 3 ms 2920 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 198 ms 12524 KB Output is correct
11 Correct 545 ms 13548 KB Output is correct
12 Correct 669 ms 13852 KB Output is correct
13 Correct 661 ms 13756 KB Output is correct
14 Correct 947 ms 14684 KB Output is correct
15 Execution timed out 2016 ms 12472 KB Time limit exceeded
16 Halted 0 ms 0 KB -