Submission #22820

#	Time	Username	Problem	Language	Result	Execution time	Memory
22820		팀명을 한번 정하면 못바꿀까? (#40)	Logistical Metropolis (KRIII5_LM)	C++14	2 / 7	2000 ms	30364 KiB

LM

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <string.h>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long ll;
typedef pair<int, int> pi;

const int MAX_N = 1e5 + 100;

struct ED {
	int x, y, c, ix;
	ED() {}
	ED(int x_, int y_, int c_, int i_) : x(x_), y(y_), c(c_), ix(i_) {}
};
int N, M;
vector<ED> all;
vector<ED> Ed[MAX_N];
int Chk[MAX_N], UNF[MAX_N];

int F(int v) { return UNF[v]==v?v:UNF[v]=F(UNF[v]); }
bool U(int a, int b) {
	a = F(a), b = F(b);
	UNF[a] = b;
	return a != b; //if union well;
}

int main() {
	scanf("%d%d", &N, &M);
	while(M--) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c);
		Ed[x].emplace_back(x, y, c, M);
		Ed[y].emplace_back(x, y, c, M);
		all.emplace_back(x, y, c, M);
	}
	sort(all.begin(), all.end(), [&](const ED &a, const ED &b) {return a.c < b.c;});
	for(int s=1; s<=N; s++) {
		for(int i=1; i<=N; i++) UNF[i] = i;
		ll ans = 0;
		for(ED &e : Ed[s]) {
			Chk[e.ix] = s;
			U(e.x, e.y);  ans += e.c;
		}
		for(ED &e : all) {
			if(Chk[e.ix] == s) continue;
			if(U(e.x, e.y)) ans += e.c;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:37:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
LM.cpp:39:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, c; scanf("%d%d%d", &x, &y, &c);
                                           ^

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