oj.uz

답안 #397525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397525 2021-05-02T10:28:21 Z blue 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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