oj.uz

Submission #122429

# Submission time Handle Problem Language Result Execution time Memory
122429 2019-06-28T07:55:50 Z 윤교준(#2990) Toll (APIO13_toll) C++14
78 / 100
 2500 ms 29620 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 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;
unsigned char str[10000055], *p=str;

const bool debug = 0;

const int MAXN = 100055;
const int MAXK = 21;

struct DJF {
	DJF(int _N) : N(_N) { ud = new int[N+5]; init(); }
	const int N;
	int *ud;

	void init() { iota(ud, ud+N+5, 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(MAXN);

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

	int p, v;

	ll sumU, sumD;
	int mxe;

	bool ign, dead;

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

struct GPH {
	GPH() : edgn(0), SWPVn(0), djf(MAXK<<2) {}

	DJF djf;
	pii PRTEV[500055]; int PRTEVn;
	int SWPV[500055], SWPVn;

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

	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 coloring(int a, int b, int c) {
		djf.init();
		for(int e;;) {
			a = djf.uf(a);
			b = djf.uf(b);
			if(a == b) break;
			if(dep[a] > dep[b]) {
				e = prte[a];
				if(edg[e].ign) edg[e].mxe = c;
				djf.uf(edg[e].p, a);
			} else {
				e = prte[b];
				if(edg[e].ign) edg[e].mxe = c;
				djf.uf(edg[e].p, b);
			}
		}
	}

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

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

	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;
		}
	}

	int 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 -1;

		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 mxei;
	}
	void rollback(int mxei, int a, int b) {
		G[a].pop_back();
		G[b].pop_back();
		edgn--;

		edg[mxei].dead = false;
		D[edg[mxei].p] -= edg[mxei].sumU;
		D[edg[mxei].v] -= edg[mxei].sumD;
	}
	void rollbackSWP(int vn) {
		for(; vn < SWPVn;) {
			SWPVn--;
			edg[SWPV[SWPVn]].swp();
		}
	}
	void rollbackPRTE(int vn) {
		for(int a, b; vn < PRTEVn;) {
			PRTEVn--;
			tie(a, b) = PRTEV[PRTEVn];
			prte[a] = b;
		}
	}

	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++) PQ[i].clear();
		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);
		}
		dep[1] = 1;
		dfssum(1, -1);
		/*
		for(int i = 1; i < n; i++) if(edg[i].dead)
			coloring(edg[i].p, edg[i].v, edg[i].mxe);
*/

		ll ret = 0;
		for(int i = n; i <= edgn; i++) if(edg[i].ign)
			ret += E[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;

	int tn = gph.SWPVn, ten = gph.PRTEVn;

	upmax(Ans, gph.getAns(sz(TV)));
	for(int i = 0; i < K; i++) {
		if((key & (1<<i)) || solveDFSchk[key | (1<<i)]) continue;
		//gph.dfs(1, -1);
		int vn = gph.SWPVn, pen = gph.PRTEVn;
		int ret = gph.addEdge(getI(E[i]), getI(F[i]));
		if(ret < 0) continue;
		solveDFS(gph, key | (1<<i));
		gph.rollback(ret, getI(E[i]), getI(F[i]));
		gph.rollbackSWP(vn);
		gph.rollbackPRTE(pen);
	}

	gph.rollbackSWP(tn);
	gph.rollbackPRTE(ten);
}

GPH tree;
void solve() {
	sort(allv(EDGV), [&](const EDG &a, const EDG &b) {
		return a.mxe < b.mxe;
	});
	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);

	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() {
	fread(str, 1, 10000055, stdin);

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

	rf(N) rf(M) rf(K)
	for(int i = 0, a, b, c; i < M; i++) {
		rf(a) rf(b) rf(c)
		EV.eb(c, pii(a, b));
	}
	for(int i = 0; i < K; i++) { rf(E[i]) rf(F[i]) }
	for(int i = 1; i <= N; i++) { rf(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;
		for(int e; v != p;) {
			e = prte[v];
			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);
	}
}

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]];
	
	treeCompress();
	colorEdges();
	dfsleaf(1);
	makeEdges();

	solve();

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

Compilation message

toll.cpp: In constructor 'GPH::GPH()':
toll.cpp:57:23: warning: 'GPH::edgn' will be initialized after [-Wreorder]
  EDG edg[MAXK*5]; int edgn;
                       ^~~~
toll.cpp:54:20: warning:   'int GPH::SWPVn' [-Wreorder]
  int SWPV[500055], SWPVn;
                    ^~~~~
toll.cpp:50:2: warning:   when initialized here [-Wreorder]
  GPH() : edgn(0), SWPVn(0), djf(MAXK<<2) {}
  ^~~
toll.cpp:54:20: warning: 'GPH::SWPVn' will be initialized after [-Wreorder]
  int SWPV[500055], SWPVn;
                    ^~~~~
toll.cpp:52:6: warning:   'DJF GPH::djf' [-Wreorder]
  DJF djf;
      ^~~
toll.cpp:50:2: warning:   when initialized here [-Wreorder]
  GPH() : edgn(0), SWPVn(0), djf(MAXK<<2) {}
  ^~~
toll.cpp: In function 'void input()':
toll.cpp:316: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, 10000055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Correct 9 ms 7140 KB Output is correct
4 Correct 9 ms 7168 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Correct 9 ms 7140 KB Output is correct
4 Correct 9 ms 7168 KB Output is correct
5 Correct 14 ms 7548 KB Output is correct
6 Correct 10 ms 7548 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Correct 9 ms 7140 KB Output is correct
4 Correct 9 ms 7168 KB Output is correct
5 Correct 14 ms 7548 KB Output is correct
6 Correct 10 ms 7548 KB Output is correct
7 Correct 271 ms 29620 KB Output is correct
8 Correct 236 ms 28176 KB Output is correct
9 Correct 261 ms 28176 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Correct 9 ms 7140 KB Output is correct
4 Correct 9 ms 7168 KB Output is correct
5 Correct 14 ms 7548 KB Output is correct
6 Correct 10 ms 7548 KB Output is correct
7 Correct 271 ms 29620 KB Output is correct
8 Correct 236 ms 28176 KB Output is correct
9 Correct 261 ms 28176 KB Output is correct
10 Execution timed out 2550 ms 28000 KB Time limit exceeded
11 Halted 0 ms 0 KB -