oj.uz

Submission #429656

# Submission time Handle Problem Language Result Execution time Memory
429656 2021-06-16T08:28:30 Z snasibov05 Swapping Cities (APIO20_swap) C++14
0 / 100
 310 ms 28384 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[y][b].s < arr[x][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[y][b].s < arr[x][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[y][b].s < arr[x][a].s)){
      |                                    ~~^~~~~~~~~~~~~~~~

Subtask #1
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 376 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 200 ms 20920 KB Output is correct
10 Correct 220 ms 25328 KB Output is correct
11 Correct 223 ms 24672 KB Output is correct
12 Correct 247 ms 26216 KB Output is correct
13 Correct 120 ms 18832 KB Output is correct
14 Correct 168 ms 20924 KB Output is correct
15 Correct 299 ms 27636 KB Output is correct
16 Correct 285 ms 26632 KB Output is correct
17 Correct 310 ms 28384 KB Output is correct
18 Correct 184 ms 20572 KB Output is correct
19 Incorrect 98 ms 7652 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
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 193 ms 18684 KB Output is correct
4 Incorrect 225 ms 19300 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 376 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Incorrect 0 ms 204 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct

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 376 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 200 ms 20920 KB Output is correct
10 Correct 220 ms 25328 KB Output is correct
11 Correct 223 ms 24672 KB Output is correct
12 Correct 247 ms 26216 KB Output is correct
13 Correct 120 ms 18832 KB Output is correct
14 Correct 168 ms 20924 KB Output is correct
15 Correct 299 ms 27636 KB Output is correct
16 Correct 285 ms 26632 KB Output is correct
17 Correct 310 ms 28384 KB Output is correct
18 Correct 184 ms 20572 KB Output is correct
19 Correct 193 ms 18684 KB Output is correct
20 Incorrect 225 ms 19300 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct