Submission #22681

#	Time	Username	Problem	Language	Result	Execution time	Memory
22681		Jongwon Party (#40)	Logistical Metropolis (KRIII5_LM)	C++14	2 / 7	46 ms	1360 KiB

LM

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

struct edg
{
    int y, c;
};

struct edg2
{
    int x, y, c;
    bool operator <(const edg2 &a) const
    {
        return c < a.c;
    }
};

std::vector<edg> arr[1001];
std::vector<edg2> sor;

int par[1001];
int rnk[1001];

int root(int x)
{
    return x == par[x] ? x : (par[x] = root(par[x]));
}

bool merge(int x, int y)
{
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;

    if(rnk[x] < rnk[y])
        par[x] = y;
    else
    {
        par[y] = x;
        if(rnk[x] == rnk[y])
            rnk[x]++;
    }
    return 1;
}
    

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int n, m, x, y, c, i, j;
    long long r;
    scanf("%d%d", &n, &m);
    for(i = 0; i<m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        arr[x].push_back({ y, c });
        arr[y].push_back({ x, c });
        sor.push_back({ x, y, c });
    }

    sort(sor.begin(), sor.end());

    for(i = 1; i<=n; i++)
    {
        r = 0;
        for(j = 1; j<=n; j++)
        {
            par[j] = j;
            rnk[j] = 0;
        }

        for(edg &e: arr[i])
            if(merge(i, e.y))
                r += e.c;

        for(edg2 &e: sor)
            if(merge(e.x, e.y))
                r += e.c;

        printf("%lld\n", r);
    }

    return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:60:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
LM.cpp:63:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &c);
                                    ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5