oj.uz

답안 #122385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122385 2019-06-28T06:44:08 Z 윤교준(#2990) 통행료 (APIO13_toll) C++14
78 / 100
 2500 ms 23500 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const bool debug = 0;

const int MAXN = 100055;
const int MAXK = 25;

struct DJF {
	DJF() { init(); }
	int ud[MAXN];

	void init() { iota(ud, ud+MAXN, 0); }
	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); }
} djf;

struct EDG {
	EDG(int p, int v, ll sumU, ll sumD, int mxe, int mne)
		: p(p), v(v), sumU(sumU), sumD(sumD), mxe(mxe), mne(mne), ign(false), dead(false) {}
	EDG(int p, int v) : p(p), v(v), ign(true) {}
	EDG() : ign(false) {}

	int p, v;

	ll sumU, sumD;
	int mxe, mne;

	bool ign, dead;

	int nxt(int i) { return p^v^i; }
	ll sums() { return sumU + sumD; }
	void swp() { swap(p, v); swap(sumU, sumD); }

	void prt() {
		printf("EDG : p=%d, v=%d, sumU=%lld, sumD=%lld, mxe=%d, mne=%d, ign=%d\n", p, v, sumU, sumD, mxe, mne, int(ign));
	}
};

struct GPH {
	GPH() : edgn(0) {
		memset(D, 0, MAXK<<5);
		memset(prte, 0, MAXK<<4);
	}

	vector<int> G[MAXK<<2];
	EDG edg[MAXK*5]; int edgn;
	set<int> PQ[MAXK<<2];
	ll D[MAXK<<2];
	int prte[MAXK<<2];

	void prt() {
		puts("GRAPH");
		printf("edgn = %d\n", edgn);
		for(int i = 1; i <= edgn; i++) {
			printf("EDG %d : ", i);
			edg[i].prt();
		}
		for(int i = 1; i < (MAXK<<2); i++) if(!G[i].empty()) {
			printf("G %d : ", i);
			for(int v : G[i]) printf("%d ", v);
			puts("");
		}
		for(int i = 1; i < (MAXK<<2); i++) if(D[i])
			printf("D %d ; %lld\n", i, D[i]);
		for(int i = 1; i < (MAXK<<2); i++) if(prte[i])
			printf("prte %d ; %d\n", i, prte[i]);
		puts("GRAPHEND");
	}

	bitset<MAXK<<2> chk;
	int lca(int a, int b) {
		if(a == b) return a;
		chk.reset();
		for(;;) {
			chk[a] = true;
			if(1 == a) break;
			a = edg[prte[a]].p;
		}
		for(;;) {
			if(chk[b]) return b;
			b = edg[prte[b]].p;
		}
	}

	void dfs(int i, int p) {
		for(int e : G[i]) {
			int v = edg[e].nxt(i);
			if(v == p) {
				prte[i] = e;
				continue;
			}
			if(edg[e].p != i) edg[e].swp();
			dfs(v, i);
		}
	}
	void dfssum(int i) {
		auto &V = PQ[i];
		for(int e : G[i]) {
			int v = edg[e].v;
			if(v == i) continue;
			dfssum(v);
			D[i] += D[v];
			if(!edg[e].ign) D[i] += edg[e].sums();

			auto &T = PQ[v];
			if(edg[e].ign) edg[e].mxe = *T.begin();
			for(int w : T) {
				auto it = V.find(w);
				if(V.end() == it) V.insert(w);
				else V.erase(it);
			}
			T.clear();
		}
	}

	void remove(int v, int e) {
		G[v].erase(find(allv(G[v]), e));
	}

	void goupWithEdge(int a, int c, int &mxe, int &mxei) {
		for(int v = a, e; v != c;) {
			e = prte[v];
			if(!edg[e].ign && mxe < edg[e].mxe) {
				mxe = edg[e].mxe;
				mxei = e;
			}
			v = edg[e].p;
		}
	}

	bool addEdge(int a, int b) {
		int c = lca(a, b);
		int mxe = -1, mxei = -1;
		goupWithEdge(a, c, mxe, mxei);
		goupWithEdge(b, c, mxe, mxei);
		if(mxei < 0) return false;

		D[edg[mxei].p] += edg[mxei].sumU;
		D[edg[mxei].v] += edg[mxei].sumD;
		edg[mxei].dead = true;
		remove(edg[mxei].p, mxei);
		remove(edg[mxei].v, mxei);

		edgn++;
		edg[edgn] = EDG(a, b);
		G[a].eb(edgn);
		G[b].eb(edgn);

		dfs(1, -1);

		return true;
	}

	void addEdge(EDG e) {
		edgn++;
		edg[edgn] = e;
		G[e.p].eb(edgn);
		G[e.v].eb(edgn);
	}

	ll getAns(int n) {
		for(int i = 1; i < n; i++) if(edg[i].dead) {
			PQ[edg[i].p].insert(edg[i].mxe);
			PQ[edg[i].v].insert(edg[i].mxe);
		}
		dfssum(1);

		ll ret = 0;
		for(int i = n; i <= edgn; i++) if(edg[i].ign) {
			ret += D[edg[i].v] * edg[i].mxe;
			if(debug) {
				printf("GETANS EDG : %d %d / %lld %d\n", edg[i].p, edg[i].v, D[edg[i].v], edg[i].mxe);
			}
		}
		return ret;
	}
};

vector<int> G[MAXN];

vector<int> TV;
vector<pii> TE;
vector<EDG> EDGV;
bitset<MAXN> chkV, chkE;

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

int A[MAXN], B[MAXN], C[MAXN];
ll D[MAXN];
int E[MAXK], F[MAXK];

ll Ans;
int N, K;


int getI(int v) { return int(lower_bound(allv(TV), v) - TV.begin()) + 1; }

bitset<1<<MAXK> solveDFSchk;
void solveDFS(GPH &gph, int key) {
	solveDFSchk[key] = true;

	for(int i = 0; i < K; i++) {
		if((key & (1<<i)) || solveDFSchk[key | (1<<i)]) continue;
		GPH nxt = gph;
		nxt.addEdge(getI(E[i]), getI(F[i]));
		solveDFS(nxt, key | (1<<i));
	}

	if(debug) {
	printf("============ solveDFS %d\n", key);
	gph.prt();
	ll t = gph.getAns(sz(TV));
	printf("Ans = %lld\n\n", t);
	upmax(Ans, t);
	} else {
		upmax(Ans, gph.getAns(sz(TV)));
	}
}

void solve() {
	GPH tree;
	for(auto e : EDGV) {
		e.p = getI(e.p);
		e.v = getI(e.v);
		tree.addEdge(e);
	}
	for(int v : TV) tree.D[getI(v)] = D[v];
	tree.dfs(1, -1);

	if(debug) {
		tree.prt();
	}

	solveDFS(tree, 0);
}


bool isin(int p, int v) { return dfo[p] <= dfo[v] && dfo[v] < dfo[p] + cnt[p]; }

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int 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];
}

void dfs(int i, int &c) {
	cnt[i] = 1; dfo[i] = ++c;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(dep[v]) continue;
		dep[v] = dep[i] + 1;
		prte[v] = e;
		prt[0][v] = i;
		dfs(v, c);
		cnt[i] += cnt[v];
	}
}

void input() {
	ios::sync_with_stdio(false);

	vector<pair<int, pii>> EV;
	int M;

	cin >> N >> M >> K;
	for(int i = 0, a, b, c; i < M; i++) {
		cin >> a >> b >> c;
		EV.eb(c, pii(a, b));
	}
	for(int i = 0; i < K; i++) cin >> E[i] >> F[i];
	for(int i = 1; i <= N; i++) cin >> D[i];

	sorv(EV); M = 0;
	for(auto &e : EV) {
		int a, b, c = e.first;
		tie(a, b) = e.second;
		if(djf.uf(a) == djf.uf(b)) continue;
		djf.uf(a, b);
		M++;
		A[M] = a; B[M] = b; C[M] = c;
		G[a].eb(M);
		G[b].eb(M);
	}
}

void treeCompress() {
	vector<int> V, VT;
	V.eb(1);
	for(int i = 0; i < K; i++) {
		V.eb(E[i]);
		V.eb(F[i]);
	}
	sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
	univ(V);

	for(int i = 1, n = sz(V); i < n; i++)
		V.eb(lca(V[i-1], V[i]));
	sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
	univ(V);

	for(int v : V) chkV[v] = true;
	TV = V; sorv(TV);

	for(int v : V) {
		for(; !VT.empty() && !isin(VT.back(), v); VT.pop_back());
		if(!VT.empty()) TE.eb(VT.back(), v);
		VT.eb(v);
	}
}

void colorEdges() {
	for(auto &e : TE) {
		int p, v; tie(p, v) = e;
		for(; v != p;) {
			chkE[prte[v]] = true;
			v = prt[0][v];
		}
	}
}

void dfsleaf(int i) {
	for(int e : G[i]) if(e != prte[i]) {
		int v = A[e]^B[e]^i;
		dfsleaf(v);
		if(chkE[e]) continue;
		D[i] += D[v];
		D[v] = 0;
	}
}

void makeEdges() {
	for(auto &ed : TE) {
		int p, v; tie(p, v) = ed;
		ll sumU = 0, sumD = 0;
		int mxe = -1, mne = INF;
		for(int e; v != p;) {
			e = prte[v];
			upmin(mne, C[e]);
			if(mxe < C[e]) {
				mxe = C[e];
				sumD += sumU;
				sumU = 0;
			}
			v = prt[0][v];
			sumU += D[v];
		}
		sumU -= D[p];
		EDGV.eb(p, ed.second, sumU, sumD, mxe, mne);
	}
}

int main() {
	input();

	if(debug) {
		for(int i = 1; i < N; i++) printf("EDG %d ; %d %d %d\n", i, A[i], B[i], C[i]);
	}

	dep[1] = 1; { int c = 0; dfs(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]];
	
	if(debug) {
		puts("DFS");
		for(int i = 1; i <= N; i++)
			printf("%d ; %d %d / %d %d %d\n", i, prt[0][i], prte[i], dep[i], cnt[i], dfo[i]);
	}
	
	treeCompress();
	colorEdges();
	dfsleaf(1);
	makeEdges();

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("D %d ; %lld\n", i, D[i]);
		printf("TV :: ");
		for(int v : TV) printf("%d ", v);
		puts("");
		printf("%d edges\n", sz(EDGV));
		for(auto &e : EDGV) {
			e.prt();
		}
	}

	solve();

	cout << Ans << endl;
	return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 13 ms 3580 KB Output is correct
6 Correct 9 ms 3708 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 13 ms 3580 KB Output is correct
6 Correct 9 ms 3708 KB Output is correct
7 Correct 506 ms 23236 KB Output is correct
8 Correct 413 ms 23172 KB Output is correct
9 Correct 502 ms 23300 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 13 ms 3580 KB Output is correct
6 Correct 9 ms 3708 KB Output is correct
7 Correct 506 ms 23236 KB Output is correct
8 Correct 413 ms 23172 KB Output is correct
9 Correct 502 ms 23300 KB Output is correct
10 Execution timed out 2538 ms 23500 KB Time limit exceeded
11 Halted 0 ms 0 KB -