oj.uz

Submission #429649

# Submission time Handle Problem Language Result Execution time Memory
429649 2021-06-16T08:23:49 Z snasibov05 Swapping Cities (APIO20_swap) C++14
13 / 100
 381 ms 29664 KB 
#include "swap.h"
#include <vector>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define oo 1000000001

struct edge{
    int u, v;
    int w;

    bool operator< (edge e) const{
        return w < e.w;
    }
};


vector<int> pr;
vector<edge> ed;
vector<int> deg;
vector<vector<int>> cmp;
vector<vector<pii>> arr;
vector<int> when;

void Union(edge e){
    deg[e.u]++; deg[e.v]++;

    int x = pr[e.u]; int y = pr[e.v];

    if (x == y){
        when[x] = min(when[x], e.w);
        return;
    }

    if (cmp[x].size() < cmp[y].size()) swap(x, y);

    for (auto node : cmp[y]){
        cmp[x].pb(node);
        pr[node] = x;
        arr[node].pb({x, e.w});
    }
    
    cmp[y].clear();
    if (when[y] != oo) when[x] = min(when[x], e.w);
    if (deg[e.u] >= 3 || deg[e.v] >= 3) when[x] = min(when[x], e.w);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    pr.resize(n);
    ed.resize(m);
    deg.resize(n);
    cmp.resize(n);
    arr.resize(n);
    when.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[i].u = u[i];
        ed[i].v = v[i];
        ed[i].w = w[i];
    }

    for (int i = 0; i < n; ++i) {
        pr[i] = i;
        cmp[i].pb(i);
        deg[i] = 0;
        arr[i].pb({i, 0});
        when[i] = oo;
    }


    sort(ed.begin(), ed.end());

    for (int i = 0; i < m; ++i) {
        Union(ed[i]);
    }

}

int getMinimumFuelCapacity(int x, int y) {

    int ans = 0;
    if (when[pr[x]] == oo) return -1;
    int cmpx = x, cmpy = y;
    int a = 0, b = 0;

    while (cmpx != cmpy || when[cmpx] == oo){
        if (a == arr[x].size() || (b != arr[y].size() && arr[x][b].s < arr[y][a].s)){
            cmpy = arr[y][b].f;
            ans = max(ans, arr[y][b++].s);
        } else {
            cmpx = arr[x][a].f;
            ans = max(ans, arr[x][a++].s);
        }
    }

    ans = max(ans, when[cmpx]);

    return ans;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (a == arr[x].size() || (b != arr[y].size() && arr[x][b].s < arr[y][a].s)){
      |             ~~^~~~~~~~~~~~~~~~
swap.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (a == arr[x].size() || (b != arr[y].size() && arr[x][b].s < arr[y][a].s)){
      |                                    ~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 165 ms 20876 KB Output is correct
10 Correct 221 ms 25320 KB Output is correct
11 Correct 210 ms 24760 KB Output is correct
12 Correct 235 ms 26340 KB Output is correct
13 Correct 128 ms 18828 KB Output is correct
14 Correct 203 ms 20928 KB Output is correct
15 Correct 292 ms 27752 KB Output is correct
16 Correct 309 ms 26652 KB Output is correct
17 Correct 282 ms 28452 KB Output is correct
18 Correct 193 ms 20580 KB Output is correct
19 Correct 93 ms 7620 KB Output is correct
20 Correct 356 ms 28684 KB Output is correct
21 Correct 325 ms 27944 KB Output is correct
22 Correct 381 ms 29664 KB Output is correct
23 Correct 252 ms 22040 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 196 ms 18676 KB Output is correct
4 Correct 213 ms 19240 KB Output is correct
5 Correct 192 ms 18960 KB Output is correct
6 Correct 190 ms 19144 KB Output is correct
7 Correct 231 ms 19160 KB Output is correct
8 Correct 203 ms 18452 KB Output is correct
9 Correct 196 ms 18960 KB Output is correct
10 Correct 220 ms 18396 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Incorrect 2 ms 460 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 165 ms 20876 KB Output is correct
11 Correct 221 ms 25320 KB Output is correct
12 Correct 210 ms 24760 KB Output is correct
13 Correct 235 ms 26340 KB Output is correct
14 Correct 128 ms 18828 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Incorrect 2 ms 460 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 165 ms 20876 KB Output is correct
10 Correct 221 ms 25320 KB Output is correct
11 Correct 210 ms 24760 KB Output is correct
12 Correct 235 ms 26340 KB Output is correct
13 Correct 128 ms 18828 KB Output is correct
14 Correct 203 ms 20928 KB Output is correct
15 Correct 292 ms 27752 KB Output is correct
16 Correct 309 ms 26652 KB Output is correct
17 Correct 282 ms 28452 KB Output is correct
18 Correct 193 ms 20580 KB Output is correct
19 Correct 196 ms 18676 KB Output is correct
20 Correct 213 ms 19240 KB Output is correct
21 Correct 192 ms 18960 KB Output is correct
22 Correct 190 ms 19144 KB Output is correct
23 Correct 231 ms 19160 KB Output is correct
24 Correct 203 ms 18452 KB Output is correct
25 Correct 196 ms 18960 KB Output is correct
26 Correct 220 ms 18396 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Incorrect 2 ms 460 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 165 ms 20876 KB Output is correct
11 Correct 221 ms 25320 KB Output is correct
12 Correct 210 ms 24760 KB Output is correct
13 Correct 235 ms 26340 KB Output is correct
14 Correct 128 ms 18828 KB Output is correct
15 Correct 203 ms 20928 KB Output is correct
16 Correct 292 ms 27752 KB Output is correct
17 Correct 309 ms 26652 KB Output is correct
18 Correct 282 ms 28452 KB Output is correct
19 Correct 193 ms 20580 KB Output is correct
20 Correct 196 ms 18676 KB Output is correct
21 Correct 213 ms 19240 KB Output is correct
22 Correct 192 ms 18960 KB Output is correct
23 Correct 190 ms 19144 KB Output is correct
24 Correct 231 ms 19160 KB Output is correct
25 Correct 203 ms 18452 KB Output is correct
26 Correct 196 ms 18960 KB Output is correct
27 Correct 220 ms 18396 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Incorrect 2 ms 460 KB Output isn't correct
32 Halted 0 ms 0 KB -