oj.uz

Submission #397525

# Submission time Handle Problem Language Result Execution time Memory
397525 2021-05-02T10:28:21 Z blue Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 353704 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])
        {
            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[u] = w;
            flag = 0;
        }
        else if(goodEdge[u] < 2e9 && goodEdge[v] == 2e9)
        {
            endpoints[ col[v] ].clear();
            for(int x: col_list[col[v]])
                goodEdge[v] = 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[u] = w;

            endpoints[ col[v] ].clear();
            for(int x: col_list[col[v]])
                goodEdge[v] = 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 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:78:21: warning: unused variable 'x' [-Wunused-variable]
   78 |             for(int x: col_list[col[u]])
      |                     ^
swap.cpp:85:21: warning: unused variable 'x' [-Wunused-variable]
   85 |             for(int x: col_list[col[v]])
      |                     ^
swap.cpp:105:21: warning: unused variable 'x' [-Wunused-variable]
  105 |             for(int x: col_list[col[u]])
      |                     ^
swap.cpp:109:21: warning: unused variable 'x' [-Wunused-variable]
  109 |             for(int x: col_list[col[v]])
      |                     ^
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 4 ms 5324 KB Output is correct
2 Correct 4 ms 5388 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 5 ms 5652 KB Output is correct
6 Correct 5 ms 5584 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 10 ms 7628 KB Output is correct
9 Correct 333 ms 37872 KB Output is correct
10 Correct 425 ms 45248 KB Output is correct
11 Correct 433 ms 44928 KB Output is correct
12 Correct 473 ms 47588 KB Output is correct
13 Execution timed out 2096 ms 353704 KB Time limit exceeded

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 4 ms 5388 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 5 ms 5652 KB Output is correct
6 Correct 5 ms 5584 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 10 ms 7628 KB Output is correct
9 Correct 4 ms 5324 KB Output is correct
10 Incorrect 6 ms 6220 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5388 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 ms 5652 KB Output is correct
7 Correct 5 ms 5584 KB Output is correct
8 Correct 5 ms 5708 KB Output is correct
9 Correct 10 ms 7628 KB Output is correct
10 Correct 333 ms 37872 KB Output is correct
11 Correct 425 ms 45248 KB Output is correct
12 Correct 433 ms 44928 KB Output is correct
13 Correct 473 ms 47588 KB Output is correct
14 Execution timed out 2096 ms 353704 KB Time limit exceeded

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 4 ms 5388 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 5 ms 5652 KB Output is correct
6 Correct 5 ms 5584 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 10 ms 7628 KB Output is correct
9 Correct 333 ms 37872 KB Output is correct
10 Correct 425 ms 45248 KB Output is correct
11 Correct 433 ms 44928 KB Output is correct
12 Correct 473 ms 47588 KB Output is correct
13 Execution timed out 2096 ms 353704 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5388 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 ms 5652 KB Output is correct
7 Correct 5 ms 5584 KB Output is correct
8 Correct 5 ms 5708 KB Output is correct
9 Correct 10 ms 7628 KB Output is correct
10 Correct 333 ms 37872 KB Output is correct
11 Correct 425 ms 45248 KB Output is correct
12 Correct 433 ms 44928 KB Output is correct
13 Correct 473 ms 47588 KB Output is correct
14 Execution timed out 2096 ms 353704 KB Time limit exceeded