oj.uz

Submission #122432

# Submission time Handle Problem Language Result Execution time Memory
122432 2019-06-28T08:07:38 Z 윤교준(#2990) Toll (APIO13_toll) C++14
100 / 100
 2195 ms 30880 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;
				a = edg[e].p;
				//djf.uf(edg[e].p, a);
			} else {
				e = prte[b];
				if(edg[e].ign) edg[e].mxe = c;
				b = edg[e].p;
				//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 = n-1; i; i--) if(edg[i].dead)
			coloring(edg[i].p, edg[i].v, edg[i].mxe);
			/*
		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:323: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 8 ms 7168 KB Output is correct
2 Correct 8 ms 7168 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7168 KB Output is correct
2 Correct 8 ms 7168 KB Output is correct
3 Correct 8 ms 7168 KB Output is correct
4 Correct 8 ms 7168 KB Output is correct
5 Correct 9 ms 7420 KB Output is correct
6 Correct 8 ms 7420 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7168 KB Output is correct
2 Correct 8 ms 7168 KB Output is correct
3 Correct 8 ms 7168 KB Output is correct
4 Correct 8 ms 7168 KB Output is correct
5 Correct 9 ms 7420 KB Output is correct
6 Correct 8 ms 7420 KB Output is correct
7 Correct 210 ms 26896 KB Output is correct
8 Correct 189 ms 26904 KB Output is correct
9 Correct 194 ms 26868 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7168 KB Output is correct
2 Correct 8 ms 7168 KB Output is correct
3 Correct 8 ms 7168 KB Output is correct
4 Correct 8 ms 7168 KB Output is correct
5 Correct 9 ms 7420 KB Output is correct
6 Correct 8 ms 7420 KB Output is correct
7 Correct 210 ms 26896 KB Output is correct
8 Correct 189 ms 26904 KB Output is correct
9 Correct 194 ms 26868 KB Output is correct
10 Correct 2195 ms 27056 KB Output is correct
11 Correct 1495 ms 30880 KB Output is correct
12 Correct 1545 ms 30760 KB Output is correct