oj.uz

Submission #428603

# Submission time Handle Problem Language Result Execution time Memory
428603 2021-06-15T13:11:03 Z snasibov05 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 9960 KB 
#include "swap.h"
#include <vector>
#include <queue>
#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 cost;

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


vector<int> pr;
vector<int> sz;
vector<bool> possible;
vector<edge> ed;
vector<int> deg;

int Find(int u){
    if (pr[u] == u) return u;
    else return pr[u] = Find(pr[u]);
}

void Union(int u, int v){
    deg[u]++; deg[v]++;

    int x = Find(u);
    int y = Find(v);

    if (x == y){
        possible[x] = true;
        return;
    }

    if (sz[x] < sz[y]) swap(x, y);

    sz[x] += sz[y];
    pr[y] = x;

    possible[x] = possible[y] | possible[x];
    if (deg[u] >= 3 || deg[v] >= 3) possible[x] = true;
}

bool check(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y && possible[x]) return true;
    else return false;
}

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

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

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

}

int getMinimumFuelCapacity(int x, int y) {

    int n = pr.size();
    int m = ed.size();
    int ans = -1;

    for (int i = 0; i < n; ++i) {
        pr[i] = i;
        sz[i] = 1;
        possible[i] = false;
    }



    for (int i = 0; i < m; ++i) {
        Union(ed[i].u, ed[i].v);
        if (check(x, y)) {
            ans = ed[i].cost;
            break;
        }
    }

    return ans;
}

Subtask #1
0 / 6.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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.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 Execution timed out 2075 ms 9960 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 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 Incorrect 1 ms 204 KB Output isn't correct
4 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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -