oj.uz

Submission #397530

# Submission time Handle Problem Language Result Execution time Memory
397530 2021-05-02T10:33:19 Z blue Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 346284 KB 
#include "swap.h"
#include <vector>
#include <algorithm>
using namespace std;

/*
Use Kruskal's algorithm.
For every node, compute sorted (by wt) list of edges that doubled its component's size.
Also compute the minimum edge wt that made it's component 'good'.

A component is good if it is not a single path.
*/

vector<int> W1;

vector<int> merges[100000]; //edge
vector<int> newcol[100000]; //color after merging
vector<int> goodEdge(100000, 2e9); //weight of smallest edge that made node's component good

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

    int I[M];
    for(int i = 0; i < M; i++) I[i] = i;
    sort(I, I+M, [] (int x, int y)
    {
        return W1[x] < W1[y];
    });

    // for(int i: I) cerr << i << ' ';
    // cerr << '\n';

    vector<int> col(N);
    vector<int> col_list[N];
    vector<int> endpoints[N];

    for(int i = 0; i < N; i++)
    {
        col[i] = i;
        col_list[i].push_back(i);

        merges[i].push_back(0);
        newcol[i].push_back(i);

        for(int e = 0; e < 2; e++)
            endpoints[i].push_back(i);
    }

    for(int i = 0; i < M; i++)
    {
        int u = U[I[i]], v = V[I[i]], w = W[I[i]];
        // cerr << "cc:\n";
        // for(int j = 0; j < N; j++)
        // {
        //     for(int q: col_list[j]) cerr << q << ' ';
        //     cerr << '\n';
        // }
        // cerr << "wt = " << w << '\n';

        if(col[u] == col[v] && goodEdge[u] == 2e9)
        {
            if(endpoints[ col[u] ].size() == 0) continue;
            for(int x: col_list[ col[u] ])
                goodEdge[x] = w;
            endpoints[ col[u] ].clear();
            continue;
        }

        if(col_list[u].size() < col_list[v].size())
            swap(u, v);


        bool flag = 1;
        if(goodEdge[u] == 2e9 && goodEdge[v] < 2e9)
        {
            endpoints[ col[u] ].clear();
            for(int x: col_list[col[u]])
                goodEdge[x] = w;
            flag = 0;
        }
        else if(goodEdge[u] < 2e9 && goodEdge[v] == 2e9)
        {
            endpoints[ col[v] ].clear();
            for(int x: col_list[col[v]])
                goodEdge[x] = w;
            flag = 0;
        }
        else if(goodEdge[u] < 2e9 && goodEdge[v] < 2e9)
            flag = 0;

        if(flag && (u == endpoints[col[u]][0] || u == endpoints[col[u]][1]) && (v == endpoints[col[v]][0] || v == endpoints[col[v]][1]))
        {
            if(u == endpoints[col[u]][1])
                swap(endpoints[col[u]][0], endpoints[col[u]][1]);

            if(v == endpoints[col[v]][1])
                swap(endpoints[col[v]][0], endpoints[col[v]][1]);

            endpoints[col[u]] = {endpoints[col[u]][1], endpoints[col[v]][1]};
        }
        else if(flag)
        {
            endpoints[ col[u] ].clear();
            for(int x: col_list[col[u]])
                goodEdge[x] = w;

            endpoints[ col[v] ].clear();
            for(int x: col_list[col[v]])
                goodEdge[x] = w;
        }

        int colV = col[v];
        for(int x: col_list[colV])
        {
            merges[x].push_back(w);
            newcol[x].push_back(col[u]);
            col_list[ col[u] ].push_back(x);
            col[x] = col[u];
        }
        col_list[colV].clear();
    }

    // for(int i = 0; i < N; i++)
    // {
    //     cerr << "i = " << i << '\n';
    //     cerr << goodEdge[i] << '\n';
    //     cerr << "merges: ";
    //     for(int m: merges[i]) cerr << m << ' ';
    //     cerr << '\n';
    //     cerr << "newcol; ";
    //     for(int n: newcol[i]) cerr << n << ' ';
    //     cerr << '\n';
    // }
}

int getMinimumFuelCapacity(int X, int Y)
{
    if(goodEdge[X] == 2e9) return -1;

    // cerr << "\n";
    // cerr << goodEdge[X] << '\n';
    // for(int i = 0; i < merges[X].size(); i++)
    // {
    //     cerr << merges[X][i] << ' ' << newcol[X][i] << '\n';
    // }
    // cerr << '\n';
    // cerr << goodEdge[Y] << '\n';
    // for(int i = 0; i < merges[Y].size(); i++)
    // {
    //     cerr << merges[Y][i] << ' ' << newcol[Y][i] << '\n';
    // }
    // cerr << '\n';


    int res = 2e9;

    for(int i = 0; i < merges[X].size(); i++)
        for(int j = 0; j < merges[Y].size(); j++)
            if(newcol[X][i] == newcol[Y][j])
                res = min(res, max(merges[X][i], merges[Y][j]));

    res = max(res, goodEdge[X]);

    return res;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0; i < merges[X].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
swap.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for(int j = 0; j < merges[Y].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5580 KB Output is correct
6 Correct 4 ms 5580 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 10 ms 7500 KB Output is correct
9 Correct 336 ms 36084 KB Output is correct
10 Correct 428 ms 43068 KB Output is correct
11 Correct 430 ms 42904 KB Output is correct
12 Correct 465 ms 45468 KB Output is correct
13 Execution timed out 2086 ms 346284 KB Time limit exceeded

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 214 ms 27652 KB Output is correct
4 Correct 219 ms 28652 KB Output is correct
5 Correct 222 ms 28256 KB Output is correct
6 Correct 218 ms 28516 KB Output is correct
7 Correct 218 ms 28544 KB Output is correct
8 Correct 217 ms 27640 KB Output is correct
9 Correct 219 ms 28276 KB Output is correct
10 Correct 217 ms 27480 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5580 KB Output is correct
6 Correct 4 ms 5580 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 10 ms 7500 KB Output is correct
9 Incorrect 4 ms 5324 KB Output isn't correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5580 KB Output is correct
6 Correct 4 ms 5580 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 10 ms 7500 KB Output is correct
9 Correct 336 ms 36084 KB Output is correct
10 Correct 428 ms 43068 KB Output is correct
11 Correct 430 ms 42904 KB Output is correct
12 Correct 465 ms 45468 KB Output is correct
13 Execution timed out 2086 ms 346284 KB Time limit exceeded

Subtask #6
0 / 27.0

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