제출 #397530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397530		blue	자매 도시 (APIO20_swap)	C++17	7 / 100	2086 ms	346284 KiB

swap

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27