oj.uz

답안 #71550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71550 2018-08-25T06:03:52 Z 윤교준(#2220) Logistical Metropolis (KRIII5_LM) C++11
2 / 7
 2000 ms 15868 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 100005;
const int MAXM = 300005;

vector<int> T[MAXN];

int hldi[MAXN], hldj[MAXN], hldo[MAXN], hldl[MAXN], hldn;
int dep[MAXN], cnt[MAXN];

int A[MAXM], B[MAXM], C[MAXM], O[MAXM];
int ud[MAXN];
bitset<MAXM> isE;

ll MSTC;
int N, M;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

void f(int i) {
	cnt[i] = 1;
	for(int e : T[i]) {
		int v = A[e] + B[e] - i;
		if(dep[v]) continue;
		dep[v] = dep[i] + 1;
		f(v);
		cnt[i] += cnt[v];
	}
}
void f0(int i, int c) {
	hldi[i] = c; hldj[i] = hldl[c]++;
	int ni = -1, nc = -1;
	for(int e : T[i]) {
		int v = A[e] + B[e] - i;
		if(dep[v] < dep[i] || cnt[v] <= nc) continue;
		ni = v; nc = cnt[v];
	}
	// TODO
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i] >> C[i];
	}
	iota(O, O+M+1, 0); sort(O+1, O+M+1, [&](int a, int b) { return C[a] < C[b]; });

	for(int i = 1; i <= N; i++) {
		ll ret = 0;
		iota(ud, ud+N+1, 0);
		for(int j = 1; j <= M; j++) if(A[j] == i || B[j] == i) {
			uf(i, A[j]);
			uf(i, B[j]);
			ret += C[j];
		}
		for(int oj = 1, j; oj <= M; oj++) {
			j = O[oj];
			if(A[j] == i || B[j] == i) continue;
			if(uf(A[j]) == uf(B[j])) continue;
			uf(A[j], B[j]);
			ret += C[j];
		}
		printf("%lld\n", ret);
	}

	/*
	iota(ud, ud+N+1, 0);
	for(int oi = 1, i; oi <= M; oi++) {
		i = O[oi];
		if(uf(A[i]) == uf(B[i])) continue;
		uf(A[i], B[i]);
		isE[i] = true;
		MSTC += C[i];
	}

	for(int i = 1; i <= M; i++) if(isE[i]) {
		T[A[i]].eb(i);
		T[B[i]].eb(i);
	}
	dep[1] = 1; f(1);

	iota(hldo, hldo+N+1, 0); sort(hldo+1, hldo+N+1, [&](int a, int b) { return cnt[a] > cnt[b]; });
	for(int oi = 1, i; oi <= N; oi++) {
		i = hldo[oi];
		if(hldi[i]) continue;
		hldn++;
		f0(i, hldn);
	}
	*/

	return 0;
}

Compilation message

LM.cpp: In function 'void f0(int, int)':
LM.cpp:47:6: warning: variable 'ni' set but not used [-Wunused-but-set-variable]
  int ni = -1, nc = -1;
      ^~

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 2812 KB Output is correct
2 Correct 108 ms 2812 KB Output is correct
3 Correct 95 ms 3016 KB Output is correct
4 Correct 100 ms 3188 KB Output is correct
5 Correct 98 ms 3300 KB Output is correct
6 Correct 105 ms 3416 KB Output is correct
7 Correct 116 ms 3592 KB Output is correct
8 Correct 116 ms 3592 KB Output is correct
9 Correct 114 ms 3592 KB Output is correct
10 Correct 112 ms 3604 KB Output is correct
11 Correct 115 ms 3608 KB Output is correct
12 Correct 113 ms 3784 KB Output is correct
13 Correct 129 ms 3832 KB Output is correct
14 Correct 114 ms 3832 KB Output is correct
15 Correct 110 ms 3832 KB Output is correct
16 Correct 63 ms 3980 KB Output is correct
17 Correct 64 ms 4024 KB Output is correct
18 Correct 79 ms 4024 KB Output is correct
19 Correct 63 ms 4152 KB Output is correct
20 Correct 59 ms 4152 KB Output is correct
21 Correct 74 ms 4152 KB Output is correct
22 Correct 79 ms 4176 KB Output is correct
23 Correct 65 ms 4408 KB Output is correct
24 Correct 71 ms 4460 KB Output is correct
25 Correct 5 ms 4460 KB Output is correct
26 Correct 5 ms 4460 KB Output is correct
27 Correct 5 ms 4460 KB Output is correct
28 Correct 23 ms 4460 KB Output is correct

Subtask #2
0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2066 ms 15868 KB Time limit exceeded
2 Halted 0 ms 0 KB -