oj.uz

Submission #597737

# Submission time Handle Problem Language Result Execution time Memory
597737 2022-07-16T18:38:08 Z Ozy Swapping Cities (APIO20_swap) C++17
7 / 100
 124 ms 17300 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define w first
#define u second.first
#define v second.second

struct x{
    lli padre;
    lli flag;
    lli prof;
    lli val;
    lli l;
    lli r;
};

lli dis[MAX+2];
lli n,m,a,b,res;
vector< pair<lli, pair<lli,lli> > >  orden;
x uf[MAX+2];

lli dfs(lli pos) {
    if (dis[pos] > 0) return dis[pos]+1;
    if (uf[pos].padre == pos) {
        dis[pos] = 1;
        return 2;
    }
    dis[pos] = dfs(uf[pos].padre);
    return dis[pos]+1;
}

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;

    rep(i,0,m-1) orden.push_back({W[i], {U[i]+1,V[i]+1} });
    sort(orden.begin(), orden.end());

    rep(i,1,n) uf[i] = {i,0,1,0,i,i};

    for (auto act : orden) {

        a = uf[act.u].padre;
        while (a != uf[a].padre) a = uf[a].padre;
        b = uf[act.v].padre;
        while (b != uf[b].padre) b = uf[b].padre;

        if (a == b) {
            if (uf[a].flag) continue;
            uf[a].flag = act.w;
        }
        else {

            if (uf[b].prof > uf[a].prof) swap(a,b);

            uf[b].val = act.w;
            uf[b].padre = a;
            if (uf[b].prof == uf[a].prof) uf[a].prof++;

            if (uf[a].flag) continue;

            if (uf[b].flag) uf[a].flag = act.w;
            else {

                if (uf[a].l == act.u && uf[b].l == act.v) uf[a].l = uf[b].r;
                else if (uf[a].l == act.u && uf[b].r == act.v) uf[a].l = uf[b].l;
                else if (uf[a].r == act.u && uf[b].l == act.v) uf[a].r = uf[b].r;
                else if (uf[a].r == act.u && uf[b].r == act.v) uf[a].r = uf[b].l;
                else {
                     uf[a].flag = act.w;
                }

            }


        }

    }

    rep(i,1,n) if (dis[i] == 0) dis[i] = dfs(i);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;

    if (dis[X] < dis[Y]) swap(X,Y);
    a = dis[X] - dis[Y];

    res = -1;
    rep(i,1,a) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
    }

    while (X != Y) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
        res = max(res,uf[Y].val);
        Y = uf[Y].padre;
    }

    while (uf[X].flag == 0) {
        res = max(res,uf[X].val);
        if (X != uf[X].padre) X = uf[X].padre;
        else return -1;
    }

    res = max(res,uf[X].flag);
    return res;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 115 ms 16784 KB Output is correct
4 Correct 95 ms 17136 KB Output is correct
5 Correct 103 ms 17196 KB Output is correct
6 Correct 124 ms 17052 KB Output is correct
7 Correct 99 ms 17300 KB Output is correct
8 Correct 98 ms 16748 KB Output is correct
9 Correct 97 ms 17044 KB Output is correct
10 Correct 97 ms 16628 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -