oj.uz

답안 #71598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71598 2018-08-25T08:14:31 Z 윤교준(#2220) Logistical Metropolis (KRIII5_LM) C++11
2 / 7
 2000 ms 47508 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;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static unsigned char str[22000022], *p=str;

const bool debug = 0;
const int MAXN = 100005;
const int MAXM = 300005;

vector<pii> Bumsoo[MAXN];
vector<int> G[MAXN], T[MAXN];

int prt[17][MAXN], prtmxe[17][MAXN];
int dep[MAXN], cnt[MAXN], dfo[MAXN];

int A[MAXM], B[MAXM], C[MAXM], O[MAXM];
int ud[MAXN], isD[MAXN], isDn;
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); }

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 0; i < 17; i++) if(dt & (1<<i)) b = prt[i][b];
	if(a == b) return a;
	for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
		a = prt[i][a]; b = prt[i][b];
	}
	return prt[0][a];
}
int upmxe(int i, int l) {
	int ret = 0;
	for(int j = 0; j < 17; j++) if(l & (1<<j)) {
		upmax(ret, prtmxe[j][i]);
		i = prt[j][i];
	}
	return ret;
}

void f(int i, int &c) {
	cnt[i] = 1; dfo[i] = ++c;
	for(int e : T[i]) {
		int v = A[e] + B[e] - i;
		if(dep[v]) continue;
		prt[0][v] = i;
		prtmxe[0][v] = C[e];
		dep[v] = dep[i] + 1;
		f(v, c);
		cnt[i] += cnt[v];
	}
}

pll dfs(int idx) {
	auto &V = Bumsoo[idx];
	if(V.empty()) {
		pll ret = (isD[idx] == isDn) ? pll(-INFLL, 0) : pll(0, -INFLL);
		if(debug) printf("DFS idx=%d : %lld / %lld\n", idx, ret.first, ret.second);
		return ret;
	}
	pll ret(0, 0); ll mx = -INFLL;
	if(isD[idx] == isDn) ret.first = -INFLL;
	for(auto &e : V) {
		pll t = dfs(e.first);
		if(isD[idx] != isDn) {
			ll q = max(t.first, t.second + e.second);
			ret.first += q;
			ret.second += q;
			upmax(mx, -q + t.second);
		} else {
			ret.second += max(t.first, t.second + e.second);
		}
		upmax(ret.first, -INFLL);
		upmax(ret.second, -INFLL);
		upmin(ret.first, INFLL);
		upmin(ret.second, INFLL);
	}
	if(isD[idx] != isDn) ret.second += mx;
	upmax(ret.first, -INFLL);
	upmax(ret.second, -INFLL);
	upmin(ret.first, INFLL);
	upmin(ret.second, INFLL);

	if(debug) printf("DFS idx=%d : %lld / %lld\n", idx, ret.first, ret.second);
	return ret;
}

int main() {
	fread(str, 1, 22000022, stdin);

	rf(N) rf(M)
	for(int i = 1; i <= M; i++) {
		rf(A[i]) rf(B[i]) rf(C[i])
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	iota(O, O+M+1, 0); sort(O+1, O+M+1, [&](int a, int b) { return C[a] < C[b]; });
	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; { int c = 0; f(1, c); }
	for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++) {
		prt[j][i] = prt[j-1][prt[j-1][i]];
		prtmxe[j][i] = max(prtmxe[j-1][i], prtmxe[j-1][prt[j-1][i]]);
	}

	iota(ud, ud+N+1, 0);
	for(int i = 1; i <= N; i++) {
		vector<int> V;
		ll ret = MSTC; isDn++;
		isD[i] = isDn; V.eb(i);
		for(int e : G[i]) {
			int v = A[e] + B[e] - i;
			ret += C[e];
			isD[v] = isDn;
			V.eb(v);
		}
		sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
		vector<pii> PV;
		for(int i = 1, n = sz(V); i < n; i++) PV.eb(lca(V[i-1], V[i]), i);
		sort(allv(PV), [&](pii a, pii b) { return dfo[a.first] > dfo[b.first]; });

		for(auto &e : PV) {
			int p, a, b;
			tie(p, a) = e;
			b = V[a]; a = V[a-1];
			a = uf(a); b = uf(b);
			if(a != p) {
				Bumsoo[p].eb(a, upmxe(a, dep[a] - dep[p]));
				uf(p, a);
			}
			if(b != p) {
				Bumsoo[p].eb(b, upmxe(b, dep[b] - dep[p]));
				uf(p, b);
			}
		}

		if(debug) {
			printf("i=%d : ", i);
			for(int v : V) printf("%d ", v);
			puts("");
			for(auto &e : PV) printf("(%d,%d) ", e.first, e.second);
			puts("");

			printf("%d / ret = %lld\n", PV.back().first, dfs(PV.back().first).second);
		}

		if(!PV.empty()) ret -= dfs(PV.back().first).second;
		printf("%lld\n", ret);

		for(int v : V) {
			ud[v] = v;
			Bumsoo[v].clear();
		}
		for(auto &e : PV) {
			int v = e.first;
			ud[v] = v;
			Bumsoo[v].clear();
		}
	}
	return 0;
}

Compilation message

LM.cpp: In function 'int main()':
LM.cpp:107:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 22000022, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 7928 KB Output is correct
2 Correct 16 ms 8040 KB Output is correct
3 Correct 17 ms 8040 KB Output is correct
4 Correct 16 ms 8108 KB Output is correct
5 Correct 16 ms 8140 KB Output is correct
6 Correct 16 ms 8140 KB Output is correct
7 Correct 15 ms 8140 KB Output is correct
8 Correct 13 ms 8204 KB Output is correct
9 Correct 17 ms 8204 KB Output is correct
10 Correct 17 ms 8204 KB Output is correct
11 Correct 15 ms 8204 KB Output is correct
12 Correct 15 ms 8248 KB Output is correct
13 Correct 16 ms 8312 KB Output is correct
14 Correct 14 ms 8312 KB Output is correct
15 Correct 16 ms 8312 KB Output is correct
16 Correct 18 ms 8312 KB Output is correct
17 Correct 14 ms 8312 KB Output is correct
18 Correct 17 ms 8312 KB Output is correct
19 Correct 14 ms 8312 KB Output is correct
20 Correct 17 ms 8312 KB Output is correct
21 Correct 16 ms 8312 KB Output is correct
22 Correct 17 ms 8312 KB Output is correct
23 Correct 14 ms 8312 KB Output is correct
24 Correct 17 ms 8312 KB Output is correct
25 Correct 9 ms 8312 KB Output is correct
26 Correct 10 ms 8312 KB Output is correct
27 Correct 11 ms 8312 KB Output is correct
28 Correct 13 ms 8312 KB Output is correct

Subtask #2
0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1739 ms 46308 KB Output is correct
2 Correct 1941 ms 46436 KB Output is correct
3 Correct 1791 ms 46436 KB Output is correct
4 Correct 1741 ms 46436 KB Output is correct
5 Correct 1786 ms 46436 KB Output is correct
6 Correct 1576 ms 46436 KB Output is correct
7 Correct 1565 ms 46436 KB Output is correct
8 Correct 1561 ms 46436 KB Output is correct
9 Correct 1388 ms 46680 KB Output is correct
10 Correct 1458 ms 46680 KB Output is correct
11 Correct 1178 ms 46780 KB Output is correct
12 Correct 1337 ms 46780 KB Output is correct
13 Correct 1545 ms 46780 KB Output is correct
14 Correct 1597 ms 46780 KB Output is correct
15 Correct 1421 ms 46780 KB Output is correct
16 Execution timed out 2001 ms 47508 KB Time limit exceeded
17 Halted 0 ms 0 KB -