oj.uz

Submission #296021

# Submission time Handle Problem Language Result Execution time Memory
296021 2020-09-10T07:45:44 Z Alexa2001 Swapping Cities (APIO20_swap) C++17
7 / 100
 137 ms 15376 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 5;
const int Nmax = 1e5 + 5;

int rang[Nmax], t[Nmax], A[Nmax], B[Nmax], up[Nmax], good[Nmax], level[Nmax];
bool chain[Nmax];

int n, m;
vector<int> v[Nmax];


int boss(int x)
{
    if(x == t[x]) return x;
    return t[x] = boss(t[x]);
}

bool endpoints(int x, int y, int a, int b)
{
    //assert(boss(a) == x && boss(b) == y);
    return (A[x] == a || B[x] == a) && (A[y] == b || B[y] == b);
}

void combine_chains(int x, int y, int a, int b)
{
    A[y] = (A[x] == a ? B[x] : A[x]);
    B[y] = (A[y] == b ? B[y] : A[y]);
}

void dfs(int node)
{
    for(auto it : v[node])
    {
        good[it] = min(good[it], max(good[node], up[it]));
        level[it] = level[node] + 1;
        dfs(it);
    }
}

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

    vector<int> ord(m);
    iota(ord.begin(), ord.end(), 0);

    sort(ord.begin(), ord.end(), [&] (int x, int y) { return W[x] < W[y]; } );

    for(int j = 0; j<n; ++j)
    {
        good[j] = inf;
        chain[j] = 1;
        A[j] = B[j] = j;
        rang[j] = 0;
        t[j] = j;
    }

    for(auto i : ord)
    {
        int x = U[i], y = V[i], cost = W[i];

        x = boss(x);
        y = boss(y);

        if(x == y)
        {
            good[x] = min(good[x], cost);
            continue;
        }

        if(rang[x] > rang[y])
        {
            swap(x, y);
            swap(U[i], V[i]);
        }

        if(rang[x] == rang[y]) ++rang[y];

        t[x] = y;
        v[y].push_back(x);
        up[x] = cost;

        if(chain[y])
        {
            if(!chain[x] || (chain[x] && !endpoints(x, y, U[i], V[i])))
                chain[y] = 0, good[y] = min(good[y], cost);
            else if(chain[x])
                combine_chains(x, y, U[i], V[i]);
        }
    }

    dfs(boss(1));
}

int getMinimumFuelCapacity(int x, int y)
{
    int ans = 0;

    while(x != y)
    {
        if(level[x] > level[y]) ans = max(ans, up[x]), x = t[x];
            else ans = max(ans, up[y]), y = t[y];
    }

    ans = max(ans, good[x]);

    if(ans == inf) return -1;
    return ans;
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 133 ms 15008 KB Output is correct
4 Correct 133 ms 15056 KB Output is correct
5 Correct 136 ms 15376 KB Output is correct
6 Correct 135 ms 15076 KB Output is correct
7 Correct 137 ms 15372 KB Output is correct
8 Correct 133 ms 15152 KB Output is correct
9 Correct 136 ms 15192 KB Output is correct
10 Correct 132 ms 15040 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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